On edge-decomposition of cubic graphs into copies of the double-star with four edges

preprint2015arXivOpen access

Abstract

A tree containing exactly two non-pendant vertices is called a double-star. Let k1k_1 and k2k_2 be two positive integers. The double-star with degree sequence (k1+1,k2+1,1,…,1)(k_1+1, k_2+1, 1, \ldots, 1) is denoted by Sk1,k2S_{k_1, k_2}. If GG is a cubic graph and has an SS-decomposition, for a double-star SS, then SS is isomorphic to S1,1S_{1,1}, S1,2S_{1,2} or S2,2S_{2,2}. It is known that a cubic graph has an S1,1S_{1,1}-decomposition if and only if it contains a perfect matching. In this paper we study the S1,2S_{1,2}-decomposition of cubic graphs. First, we present some necessary conditions for the existence of an S1,2S_{1,2}-decomposition in cubic graphs. Then we prove that every {C3,C5,C7}\{C_3, C_5, C_7\}-free cubic graph of order nn with α(G)=3n8α(G)= \frac{3n}{8} has an S1,2S_{1,2}-decomposition, where α(G)α(G) denotes the independence number of GG. Finally, we obtain some results on the S1,r−1S_{1,r-1}-decomposition of rr-regular graphs.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.