PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2015 | 35 | 4 | 733-754
Tytuł artykułu

Rainbow Tetrahedra in Cayley Graphs

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
35
Numer
4
Strony
733-754
Opis fizyczny
Daty
wydano
2015-11-01
otrzymano
2014-11-06
poprawiono
2015-02-27
zaakceptowano
2015-02-27
online
2015-11-10
Twórcy
Bibliografia
  • [1] R. Aharoni and E. Berger, Rainbow matchings in r-partite r-graphs, Electron. J. Combin. 16(1) (2009) # R119.
  • [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]
  • [3] J. Bar´at and I.M. Wanless, Rainbow matchings and transversals, Australas. J. Com- bin. 59 (2014) 211-217.
  • [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]
  • [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]
  • [6] I.J. Dejter, Asymptotic diameter of graphs, preprint, http:\home.coqui.net\dejterij\appendix.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]
  • [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]
  • [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]
  • [12] A.V. Kelarev, Labelled Cayley graphs and minimal automata, Australas. J. Combin. 30 (2004) 95-101.
  • [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]
  • [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.
  • [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]
  • [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]
  • [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]
  • [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]
  • [20] G. Wang, Rainbow matchings in properly edge-colored graphs, Electron. J. Combin. 18(1) (2011) #162.
  • [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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1834
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.