Rainbow Tetrahedra in Cayley Graphs

Italo J. Dejter

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 4, page 733-754
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Italo J. Dejter. "Rainbow Tetrahedra in Cayley Graphs." Discussiones Mathematicae Graph Theory 35.4 (2015): 733-754. <http://eudml.org/doc/276027>.

@article{ItaloJ2015,
abstract = {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.},
author = {Italo J. Dejter},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {rainbow triangles; rainbow tetrahedra; Cayley graphs},
language = {eng},
number = {4},
pages = {733-754},
title = {Rainbow Tetrahedra in Cayley Graphs},
url = {http://eudml.org/doc/276027},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Italo J. Dejter
TI - Rainbow Tetrahedra in Cayley Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 4
SP - 733
EP - 754
AB - 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.
LA - eng
KW - rainbow triangles; rainbow tetrahedra; Cayley graphs
UR - http://eudml.org/doc/276027
ER -

References

top
  1. [1] R. Aharoni and E. Berger, Rainbow matchings in r-partite r-graphs, Electron. J. Combin. 16(1) (2009) # R119. Zbl1186.05118
  2. [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] Zbl1037.05033
  3. [3] J. Bar´at and I.M. Wanless, Rainbow matchings and transversals, Australas. J. Com- bin. 59 (2014) 211-217. Zbl1296.05159
  4. [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] Zbl0856.05038
  5. [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] Zbl0890.05031
  6. [6] I.J. Dejter, Asymptotic diameter of graphs, preprint, http:.coqui.net.pdf. 
  7. [7] L. Fejes Toth, Regular Figures (Pergamon Press, Oxford, 1964). 
  8. [8] A. Frieze and M. Krivelevich, On rainbow trees and cycles, Electron. J. Combin. 15 #R59. 
  9. [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] Zbl1290.05075
  10. [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] Zbl1107.05083
  11. [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] Zbl1206.05050
  12. [12] A.V. Kelarev, Labelled Cayley graphs and minimal automata, Australas. J. Combin. 30 (2004) 95-101. Zbl1152.68482
  13. [13] A.V. Kelarev, Graph Algebras and Automata (M. Dekker, New York, 2003). 
  14. [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] Zbl1241.05115
  15. [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. Zbl1188.05063
  16. [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] Zbl1225.68137
  17. [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] Zbl1272.05056
  18. [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] Zbl1282.05190
  19. [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] Zbl06086129
  20. [20] G. Wang, Rainbow matchings in properly edge-colored graphs, Electron. J. Combin. 18(1) (2011) #162. Zbl1230.05137
  21. [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] Zbl1017.05049

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.