Article in volume
Authors:
Title:
More aspects of arbitrarily partitionable graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1237-1261
Received: 2020-03-09 , Revised: 2020-06-08 , Accepted: 2020-06-08 , Available online: 2020-07-15 , https://doi.org/10.7151/dmgt.2343
Abstract:
A graph $G$ of order $n$ is arbitrarily partitionable (AP) if, for every
sequence $(n_1,\dots,n_p)$ partitioning $n$, there is a partition
$(V_1,\dots,V_p)$ of $V(G)$ such that $G[V_i]$ is a connected $n_i$-graph for
$i=1,\dots,p$. The property of being AP is related to other well-known graph
notions, such as perfect matchings and Hamiltonian cycles, with which it shares
several properties. This work is dedicated to studying two aspects behind AP
graphs.
On the one hand, we consider algorithmic aspects of AP graphs, which received
some attention in previous works. We first establish the NP-hardness of the
problem of partitioning a graph into connected subgraphs following a given
sequence, for various new graph classes of interest. We then prove that the
problem of deciding whether a graph is AP is in NP for several classes of
graphs, confirming a conjecture of Barth and Fournier for these.
On the other hand, we consider the weakening to APness of sufficient conditions
for Hamiltonicity. While previous works have suggested that such conditions can
sometimes indeed be weakened, we here point out cases where this is not true.
This is done by considering conditions for Hamiltonicity involving squares of
graphs, and claw- and net-free graphs.
Keywords:
arbitrarily partitionable graphs, partition into connected subgraphs, Hamiltonicity
References:
- D. Barth, O. Baudon and J. Puech, Decomposable trees: a polynomial algorithm for tripodes, Discrete Appl. Math. 119 (2002) 205–216.
https://doi.org/10.1016/S0166-218X(00)00322-X - D. Barth and H. Fournier, A degree bound on decomposable trees, Discrete Math. 306 (2006) 469–477.
https://doi.org/10.1016/j.disc.2006.01.006 - O. Baudon, J. Bensmail, F. Foucaud and M. Pilśniak, Structural properties of recursively partitionable graphs with connectivity $2$, Discuss. Math. Graph Theory 37 (2017) 89–115.
https://doi.org/10.7151/dmgt.1925 - O. Baudon, F. Gilbert and M. Woźniak, Recursively arbitrarily vertex-decomposable graphs, Opuscula Math. 32 (2012) 689–706.
https://doi.org//10.7494/OpMath.2012.32.4.689 - J. Bensmail, Partitions and decompositions of graphs, PhD. Thesis (Université de Bordeaux, France, 2014).
- J. Bensmail, On the complexity of partitioning a graph into a few connected subgraphs, J. Comb. Optim. 30 (2015) 174–187.
https://doi.org/10.1007/s10878-013-9642-8 - J. Bensmail, On three polynomial kernels of sequences for arbitrarily partitionable graphs, Discrete Appl. Math. 202 (2016) 19–29.
https://doi.org/10.1016/j.dam.2015.08.016 - J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111–135.
https://doi.org/10.1016/0012-365X(76)90078-9 - S. Brandt, Finding vertex decompositions in dense graphs (2013), personal communication.
- H. Broersma, D. Kratsch and G.J. Woeginger, Fully decomposable split graphs, European J. Combin. 34 (2013) 567–575.
https://doi.org/10.1016/j.ejc.2011.09.044 - M. Dell'Amico and S. Martello, Reduction of the three-partition problem, J. Comb. Optim. 3 (1999) 17–30.
https://doi.org/10.1023/A:1009856820553 - M.E. Dyer and A.M. Frieze, On the complexity of partitioning graphs into connected subgraphs, Discrete Appl. Math. 10 (1985) 139–153.
https://doi.org/10.1016/0166-218X(85)90008-3 - J. Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965) 449–467.
https://doi.org/10.4153/CJM-1965-045-4 - R. Faudree, E. Flandrin and Z. Ryjáček, Claw-free graphs–-A survey, Discrete Math. 164 (1997) 87–147.
https://doi.org/10.1016/S0012-365X(96)00045-3 - H. Fleischner, In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts, Monatsh. Math. 82 (1976) 125–149.
https://doi.org/10.1007/BF01305995 - M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman Co., New York, 1990).
- E. Győri, On division of graphs to connected subgraphs, in : Combinatorics Proc. 5th Hungarian Colloq. (1976) 485–494.
- M. Horňák, A. Marczyk, I. Schiermeyer and M. Woźniak, Dense arbitrarily vertex decomposable graphs, Graphs Combin. 28 (2012) 807–821.
https://doi.org/10.1007/s00373-011-1077-3 - M. Horňák, Zs. Tuza and M. Woźniak, On-line arbitrarily vertex decomposable trees, Discrete Appl. Math. 155 (2007) 1420–1429.
https://doi.org/10.1016/j.dam.2007.02.011 - R. Kalinowski, M. Pilśniak, I. Schiermeyer and M. Woźniak, Dense arbitrarily partitionable graphs, Discuss. Math. Graph Theory 36 (2016) 5–22.
https://doi.org/10.7151/dmgt.1833 - L. Lovász, A homology theory for spanning trees of a graph, Acta Math. Acad. Sci. Hungar. 30 (1977) 241–251.
https://doi.org/10.1007/BF01896190 - A. Marczyk, An Ore-type condition for arbitrarily vertex decomposable graphs, Discrete Math. 309 (2009) 3588–3594.
https://doi.org/10.1016/j.disc.2007.12.066 - O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55.
https://doi.org/10.2307/2308928 - R. Ravaux, Graphes arbitrairement partitionnables: propriétés structurelles et algorithmiques, Ph.D. Thesis (Université de Versailles Saint-Quentin, France, 2009).
Close