2024/09/05 by Caro, Yair, Davila, Randy, Pepper, Ryan
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2409.03233
Let G be a simple graph and let L(G) denote the line graph of G. A p-independent set in G is a set of vertices S ⊆ V(G) such that the subgraph induced by S has maximum degree at most p. The p-independence number of G, denoted by αp(G), is the cardinality of a maximum p-independent set in G. In this paper, and motivated by the recent result that independence number is at most matching number for regular graphs~\citeCaDaPe2020, we investigate which values of the non-negative integers p, q, and r have the property that αp(G) ≤ αq(L(G)) for all r-regular graphs. Triples (p, q, r) having this property are called valid α-triples. Among the results we prove are: \beginitemize \item (p, q, r) is valid α-triple for p ≥ 0, q ≥ 3 , and r≥ 2. \item (p, q, r) is valid α-triple for p ≤ q < 3 and r≥ 2. \item (p, q, r) is valid α-triple for p ≥ 0, q = 2, and r even. \item (p, q, r) is valid α-triple for p ≥ 0, q = 2, and r odd with r = max \ 3, (17(p+1))/(16) \. \enditemize We also show a close relation between undetermined possible valid α-triples, the Linear Aboricity Conjecture, and the Path-Cover Conjecture.