×

Unique square property, equitable partitions, and product-like graphs. (English) Zbl 1281.05115

Summary: Equivalence relations on the edge set of a graph \(G\) that satisfy restrictive conditions on chordless squares play a crucial role in the theory of Cartesian graph products and graph bundles. We show here that such relations in a natural way induce equitable partitions on the vertex set of \(G\), which in turn give rise to quotient graphs that can have a rich product structure even if \(G\) itself is prime.

MSC:

05C76 Graph operations (line graphs, products, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abello, J.; Fellows, M. R.; Stillwell, J. C., On the complexity and combinatorics of covering finite complexes, Australas. J. Combin., 4, 103-112 (1991) · Zbl 0763.05035
[2] Bachman, R.; Fredette, E.; Fuller, J.; Landry, M.; Opperman, M.; Tamon, C.; Tollefson, A., Perfect state transfer on quotient graphs, Quantum Inf. Comput., 12, 3-4, 293-313 (2012) · Zbl 1256.81018
[3] Feder, T., Product graph representations, J. Graph Theory, 16, 5, 467-488 (1992) · Zbl 0766.05092
[4] Feigenbaum, J.; Hershberger, J.; Schäffer, A. A., A polynomial time algorithm for finding the prime factors of Cartesian-product graphs, Discrete Appl. Math., 12, 123-138 (1985) · Zbl 0579.68028
[5] Fekete, Z.; Szabó, J., Equitable partitions into spanning trees in a graph, Electron. J. Combin., 18, P221 (2011) · Zbl 1243.05196
[6] Fiala, J.; Paulusma, D.; Telle, J. A., Locally constrained graph homomorphisms and equitable partitions, European J. Combin., 29, 4, 850-880 (2008) · Zbl 1205.05141
[7] Ge, Y.; Greenberg, B.; Perez, O.; Tamon, C., Perfect state transfer, graph products and equitable partitions, Int. J. Quantum Inf., 9, 3, 823-842 (2011) · Zbl 1222.81133
[8] Godsil, C.; McKay, B., Feasibility conditions for the existence of walk-regular graphs, Linear Algebra Appl., 30, 51-61 (1980) · Zbl 0452.05045
[9] Graham, R. L.; Winkler, P. M., Isometric embeddings of graphs, Proc. Natl. Acad. Sci. USA, 81, 7259-7260 (1984) · Zbl 0554.05057
[10] Hammack, R.; Imrich, W.; Klavžar, S., Handbook of Product Graphs (2011), CRC Press: CRC Press Boca Raton · Zbl 1283.05001
[11] Hellmuth, M., A local prime factor decomposition algorithm, Discrete Math., 311, 12, 944-965 (2011) · Zbl 1223.05230
[12] Hellmuth, M.; Imrich, W.; Klöckl, W.; Stadler, P. F., Approximate graph products, European J. Combin., 30, 1119-1133 (2009) · Zbl 1210.05125
[13] Hellmuth, M.; Imrich, W.; Klöckl, W.; Stadler, P. F., Local algorithms for the prime factorization of strong product graphs, Math. Comput. Sci., 2, 4, 653-682 (2009) · Zbl 1205.05222
[14] Hellmuth, M.; Imrich, W.; Kupka, T., Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs, Math. Comput. Sci., 7, 255-273 (2013) · Zbl 1319.68157
[15] Husemoller, D., Fibre Bundles (1993), Springer: Springer Heidelberg · Zbl 0794.55001
[16] Imrich, W.; Pisanski, T.; Žerovnik, J., Recognizing Cartesian graph bundles, Discrete Math., 167, 393-403 (1997) · Zbl 0876.05094
[17] Imrich, W.; Žerovnik, J., Factoring Cartesian-product graphs, J. Graph Theory, 18, 557-567 (1994) · Zbl 0811.05054
[18] Pisanski, T.; Shawe-Taylor, J.; Vrabec, J., Edge-colorability of graph bundles, J. Combin. Theory Ser. B, 35, 12-19 (1983) · Zbl 0505.05034
[19] Pisanski, T.; Zmazek, B.; Žerovnik, J., An algorithm for k-convex closure and an application, Int. J. Comput. Math., 78, 1, 1-11 (2001) · Zbl 0983.05075
[20] Sabidussi, G., Graph multiplication, Math. Z., 72, 446-457 (1960) · Zbl 0093.37603
[21] Schwenk, A. J., Computing the characteristic polynomial of a graph, (Graphs and Combinatorics. Graphs and Combinatorics, Lect. Notes Math., vol. 406 (1974), Springer: Springer Heidelberg, D), 153-172
[22] Vizing, V. G., The Cartesian product of graphs, Vyčisl. Syst.. Vyčisl. Syst., Comp. El. Syst., 2, 352-365 (1966), English translation in
[23] Zmazek, B.; Žerovnik, J., Algorithm for recognizing Cartesian graph bundles, Discrete Appl. Math., 120, 275-302 (2002) · Zbl 1004.05055
[24] Zmazek, B.; Žerovnik, J., Unique square property and fundamental factorizations of graph bundles, Discrete Math., 244, 551-561 (2002) · Zbl 0989.05088
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.