Article in press
Authors:
Title:
The tree-achieving set and non-separating independent set problem of subcubic graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-01-20 , Revised: 2023-09-02 , Accepted: 2023-09-04 , Available online: 2023-10-12 , https://doi.org/10.7151/dmgt.2522
Abstract:
The decycling number $\nabla (G)$ (respectively, tree-achieving number
$\nabla_{T} (G)$) of a graph $G$ is the smallest number of vertices whose
deletion yields a forest (respectively, tree). Obviously, $\nabla_{T}(G)\geq \nabla(G)$
for all graphs. A graph is cubic (respectively, subcubic ) if every vertex has degree
three (respectively, at most three). A non-separating independent set is an independent
vertices set whose deletion yields a connected subgraph. The nsis number
$\mathcal{Z}(G)$ is the maximum cardinality of a non-separating independent set.
In this article, we present a sufficient and necessary condition for
$\nabla_{T}(G)=\nabla(G)$ in cubic graphs. That is $\nabla_{T}(G)=\nabla(G)$
if and only if there exists a Xuong-tree [J.L. Gross and R.G. Rieper, Local
extrema in genus-stratified graphs, J. Graph Theory 15 (1991) 153–171]
$T_{X}$ of $G$ such that every odd component
of $G-E(T_{X})$ contains at least three edges. Further, we give a formula for
$\mathcal{Z}(G)$ in subcubic graphs: there is a Xuong-tree $T_{X}$ of $G$ such
that $\alpha_{1}(T_{X})=\mathcal{Z}(G)$, where $\alpha_{1}(T_{X})$ is the
independence number of the subgraph of $G$ induced by leaves of $T_{X}$.
Keywords:
tree-achieving number, decycling number, nsis number, Xuong-tree
References:
- J.A. Bondy, G. Hopkins and W. Staton, Lower bounds for induced forests in cubic graphs, Canad. Math. Bull. 30 (1987) 193–199.
https://doi.org/10.4153/CMB-1987-028-5 - F.Y. Cao and H. Ren, Nonseparating independent sets of Cartesian product graphs, Taiwanese J. Math. 24 (2020) 1–17.
https://doi.org/10.11650/tjm/190303 - P. Erdős, M. Saks and V.T. Sós, Maximum induced trees in graphs, J. Combin. Theory Ser. B 41 (1986) 61–79.
https://doi.org/10.1016/0095-8956(86)90028-6 - J.L. Gross and T.W. Tucker, Topological Graph Theory (Wiley-lnterscience, New York, 1987).
- J.L. Gross and R.G. Rieper, Local extrema in genus-stratified graphs, J. Graph Theory 15 (1991) 159–171.
https://doi.org/10.1002/jgt.3190150205 - Y.Q. Huang and Y.P. Liu, Maximum genus and maximum nonseparating independent set of a $3$-regular graph, Discrete Math. 176 (1997) 149–158.
https://doi.org/10.1016/S0012-365X(96)00299-3 - R.M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, R.E. Miller, J.W. Thatcher and J.D. Bohlinger (Ed(s)), (Springer, Boston MA 1972) 85–103.
https://doi.org/10.1007/978-1-4684-2001-2_9 - S.D. Long and H. Ren, The decycling number and maximum genus of cubic graphs, J. Graph Theory 88 (2018) 375–384.
https://doi.org/10.1002/jgt.22218 - H. Moser, Exact Algorithms for Generalizations of Vertex Cover, Masters' Thesis (Friedrich-Schiller-Universität Jena, 2005).
- B. Mohar and C. Thomasen, Graphs on Surfaces (Johns Hopkins University Press, Baltimore and London, 2001).
https://doi.org/10.56021/9780801866890 - E. Speckenmeyer, On feedback vertex sets and nonseparating independent sets in cubic graphs, J. Graph Theory 12 (1988) 405–412.
https://doi.org/10.1002/jgt.3190120311 - K.X. Xu, Z.Q. Zheng and K.Ch. Das, Extremal t-apex trees with respect to matching energy, Complexity 21 (2016) 238–247.
https://doi.org/10.1002/cplx.21651 - N.H. Xuong, How to determine the maximum genus of a graph, J. Combin. Theory Ser. B 26 (1979) 217–225.
https://doi.org/10.1016/0095-8956(79)90058-3
Close