No Detail Found!

Decomposition of 4k-regular graphs into k 4-regular K5-free and (K5 - e)-free subgraphs

Author(s)
Rachel Johnson Department of Mathematics, Illinois State University,Normal, IL 61790-4520,USA
David Mendell Department of Mathematics, Illinois State University,Normal, IL 61790-4520,USA
Samantha Norris Department of Mathematics, Illinois State University,Normal, IL 61790-4520,USA
Michael J. Plantholty Department of Mathematics, Illinois State University,Normal, IL 61790-4520,USA
Shailesh K. Tipnis Department of Mathematics, Illinois State University,Normal, IL 61790-4520,USA
Abstract
Let G be a 4k-regular graph with k 2. We show that G can be decomposed into k 4-regular spanning subgraphs G1; G2; : : : ; Gk, each of which does not contain an induced subgraph that is isomorphic to K5 or K5 e. We then use a result of Heinrich et al. [J. Graph Theory 31 (1999) 135-143] which provides a triangle-free Euler tour in each of G1; G2; : : : ; Gk to show that G has a triangle-free Euler tour. In the case when m is even, our results imply a result by Oksimets [Ph.D thesis, Umea° University, Umea° , 2003] which states that every connected 2m-regular graph G with m 2 and jE(G)j divisible by 3 can be decomposed into paths of length 3.
Publication Details
Page(s) 32-37
Published Journal: Discrete Mathematics Letters, Volume: 6, Issue: 0, Year: 2021

Request the full text from PASTIC

Keywords
forbidden subgraph, Decomposition, Eulerian
References
Bertram E.,Horak P. .1997 .-regular graphs into triangle-free 2-factors. , 10 : 309-317.
Csaba B.,D. B.,Lo A.,Osthus D.,Treglown A. . .Proof of the 1-factorization and Hamilton Decomposition Conjectures, Mem. Amer. Math. Soc, 244(2016) : 1154.
Harary F.,Addison-Wesley F. .1969 .. , : .
Heinrich K.,Yu M. .1999 .-decompositions of regular graphs. J. Graph Theory, 31 : 135-143.
Oksimets N. .2003 .A Characterization of Eulerian Graphs with Triangle-Free Euler Tours. Ph.D thesis, : .
Petersen J.,Biggs E. K.,Lloyd E. K. .1986 .Die Theorie der regula¨ren graphs. Graph Theory 1736-1936, 15 : 190-220.
Robinson R. W.,Wormald N.C. .1994 .Almost alll regular graphs are Hamiltonian. Random Structures Algorithms, 5 : 363-374.
West D. B. .2007 .. , : .
0

Citations

0

Downloads

17

Views