Rainbow Tetrahedra in Cayley Graphs
Italo J. Dejter
Discussiones Mathematicae Graph Theory, Tome 35 (2015), p. 733-754 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

Let Γn be the complete undirected Cayley graph of the odd cyclic group Zn. Connected graphs whose vertices are rainbow tetrahedra in Γn are studied, with any two such vertices adjacent if and only if they share (as tetrahedra) precisely two distinct triangles. This yields graphs G of largest degree 6, asymptotic diameter |V (G)|1/3 and almost all vertices with degree: (a) 6 in G; (b) 4 in exactly six connected subgraphs of the (3, 6, 3, 6)-semi- regular tessellation; and (c) 3 in exactly four connected subgraphs of the {6, 3}-regular hexagonal tessellation. These vertices have as closed neigh- borhoods the union (in a fixed way) of closed neighborhoods in the ten respective resulting tessellations.

Publié le : 2015-01-01
EUDML-ID : urn:eudml:doc:276027 
@article{bwmeta1.element.doi-10_7151_dmgt_1834,
     author = {Italo J. Dejter},
     title = {Rainbow Tetrahedra in Cayley Graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {35},
     year = {2015},
     pages = {733-754},
     zbl = {1327.05106},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1834}
}

Italo J. Dejter. Rainbow Tetrahedra in Cayley Graphs. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 733-754. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1834/

[1] R. Aharoni and E. Berger, Rainbow matchings in r-partite r-graphs, Electron. J. Combin. 16(1) (2009) # R119. | Zbl 1186.05118

[2] N. Alon, T. Jiang, Z. Miller and D. Pritikin, Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints, J. Random Structures Algorithms 23 (2003) 409-433. doi:10.1002/rsa.10102[Crossref] | Zbl 1037.05033

[3] J. Bar´at and I.M. Wanless, Rainbow matchings and transversals, Australas. J. Com- bin. 59 (2014) 211-217. | Zbl 1296.05159

[4] I.J. Dejter, TMC tetrahedral types MOD 2k + 1 and their structure graphs, Graphs Combin. 12 (1996) 163-178. doi:10.1007/BF01858451[Crossref] | Zbl 0856.05038

[5] I.J. Dejter, H. Hevia and O. Serra, Hidden Cayley graph structures, Discrete Math. 182 (1998) 69-83. doi:10.1016/S0012-365X(97)00134-9[Crossref] | Zbl 0890.05031

[6] I.J. Dejter, Asymptotic diameter of graphs, preprint, http:.coqui.net.pdf.

[7] L. Fejes Toth, Regular Figures (Pergamon Press, Oxford, 1964).

[8] A. Frieze and M. Krivelevich, On rainbow trees and cycles, Electron. J. Combin. 15 #R59.

[9] A. Halperin, C. Magnant and K. Pula, A decomposition of Gallai multigraphs, Dis- cuss. Math. Graph Theory 34 (2014) 331-352. doi:10.7151/dmgt.1740[Crossref] | Zbl 1290.05075

[10] S. Janson and N. Wormald, Rainbow Hamilton cycles in random regular graphs, Random Structures Algorithms 30 (2007) 35-49. doi:10.1002/rsa.20146[Crossref] | Zbl 1107.05083

[11] A.V. Kelarev, J. Ryan and J. Yearwood, Cayley graphs as classiffiers for data min- ing: The influence of asymmetries, Discrete Math. 309 (2009) 5360-5369. doi:10.1016/j.disc.2008.11.030[WoS][Crossref] | Zbl 1206.05050

[12] A.V. Kelarev, Labelled Cayley graphs and minimal automata, Australas. J. Combin. 30 (2004) 95-101. | Zbl 1152.68482

[13] A.V. Kelarev, Graph Algebras and Automata (M. Dekker, New York, 2003).

[14] A.V. Kostochka and M. Yancey, Large rainbow matchings in edge-colored graphs, Combin. Probab. Comput. 21 (2012) 255-263. doi:10.1017/S0963548311000605[Crossref] | Zbl 1241.05115

[15] T.D. LeSaulnier, C. Stocker, P.S. Wenger and D.B. West, Rainbow matching in edge-colored graphs, Electron. J. Combin. 17 (2010) #N26. | Zbl 1188.05063

[16] A. Monti and B. Sinaimeri, Rainbow graph splitting, Theoret. Comput. Sci. 412 (2011) 5315-5324. doi:10.1016/j.tcs.2011.06.004[WoS][Crossref] | Zbl 1225.68137

[17] S. Oh, H. Yoo and T. Yun, Rainbow graphs and switching classes, SIAM J. Discrete Math. 27 1106-1111. doi:10.1137/110855089[Crossref][WoS] | Zbl 1272.05056

[18] G. Perarnau and O. Serra, Rainbow matchings in complete bipartite graphs: existence and counting, Combin. Probab. Comput. 22 (2013) 783-799. doi:10.1017/S096354831300028X[Crossref] | Zbl 1282.05190

[19] L. Sunil Chandran and D. Rajendraprasad, Rainbow colouring of split and threshold graphs, in: Lectures Notes in Comput. Sc. 7434 (2012) 181-192. doi:10.1007/978-3-642-32241-9 16[Crossref] | Zbl 06086129

[20] G. Wang, Rainbow matchings in properly edge-colored graphs, Electron. J. Combin. 18(1) (2011) #162. | Zbl 1230.05137

[21] A.J. Woldar, Rainbow graphs, in: Codes and Designs, K.T. Arasu, A. Seress, Eds., (deGruyter, Berlin, 2002). doi:10.1515/9783110198119.313 [Crossref] | Zbl 1017.05049