期刊
DISCUSSIONES MATHEMATICAE GRAPH THEORY
卷 43, 期 2, 页码 385-399出版社
UNIV ZIELONA GORA
DOI: 10.7151/dmgt.2371
关键词
odd induced subgraph; subcubic graphs; claw-free graphs; line graphs; independent set
类别
In this paper, we investigate the partition problem of connected graphs with even order, proving that for a connected subcubic graph or a connected planar graph with even order, the minimum number of odd induced subgraphs in the partition does not exceed 4. We also demonstrate that for a tree of even order, the minimum number of odd induced subgraphs does not exceed 2, and for a unicyclic graph of even order, it does not exceed 3. Additionally, we prove that if the graph is claw-free, the vertex set can be partitioned into at most |Δ(G)|-1 induced forests and possibly one independent set. Furthermore, we show that the vertex set of the line graph of a tree can be partitioned into at most two odd induced subgraphs and possibly one independent set.
A graph G is called an odd (even) graph if for every vertex v & ISIN; V (G), dG(v) is odd (even). Let G be a graph of even order. Scott in 1992 proved that the vertices of every connected graph of even order can be partitioned into some odd induced forests. We denote the minimum number of odd induced subgraphs which partition V (G) by od(G). If all of the subgraphs are forests, then we denote it by odF(G). In this paper, we show that if G is a connected subcubic graph of even order or G is a connected planar graph of even order, then odF(G) < 4. Moreover, we show that for every tree T of even order odF(T) < 2 and for every unicyclic graph G of even order odF(G) < 3. Also, we prove that if G is claw-free, then V (G) can be partitioned into at most & UDelta;(G) -1 induced forests and possibly one indepen-dent set. Furthermore, we demonstrate that the vertex set of the line graph of a tree can be partitioned into at most two odd induced subgraphs and possibly one independent set.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据