Displaying similar documents to “On Decomposing Regular Graphs Into Isomorphic Double-Stars”

On Double-Star Decomposition of Graphs

Saieed Akbari, Shahab Haghi, Hamidreza Maimani, Abbas Seify (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A tree containing exactly two non-pendant vertices is called a double-star. A double-star with degree sequence (k1 + 1, k2 + 1, 1, . . . , 1) is denoted by Sk1,k2. We study the edge-decomposition of graphs into double-stars. It was proved that every double-star of size k decomposes every 2k-regular graph. In this paper, we extend this result by showing that every graph in which every vertex has degree 2k + 1 or 2k + 2 and containing a 2-factor is decomposed into Sk1,k2 and Sk1−1,k2,...

Polynomial time algorithms for two classes of subgraph problem

Sriraman Sridharan (2008)

RAIRO - Operations Research

Similarity:

We design a polynomial time algorithm for finding a -1)- regular subgraph in a -regular graph without any induced star (claw-free). A polynomial time algorithm for finding a cubic subgraph in a 4-regular locally connected graph is also given. A family of -regular graphs with an induced star (, not containing any (-1)-regular subgraph is also constructed.