DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

J. Bensmail

Julien Bensmail

Université Côte d'Azur

email: julien.bensmail.phd@gmail.com

0000-0002-9292-394X

B. Li

Binlong Li

email: libinlong@mail.nwpu.edu.cn

Title:

More aspects of arbitrarily partitionable graphs

PDF

Source:

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:

  1. 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
  2. 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
  3. 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
  4. 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
  5. J. Bensmail, Partitions and decompositions of graphs, PhD. Thesis (Université de Bordeaux, France, 2014).
  6. 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
  7. 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
  8. 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
  9. S. Brandt, Finding vertex decompositions in dense graphs (2013), personal communication.
  10. 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
  11. 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
  12. 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
  13. J. Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965) 449–467.
    https://doi.org/10.4153/CJM-1965-045-4
  14. 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
  15. 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
  16. 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).
  17. E. Győri, On division of graphs to connected subgraphs, in : Combinatorics Proc. 5th Hungarian Colloq. (1976) 485–494.
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55.
    https://doi.org/10.2307/2308928
  24. R. Ravaux, Graphes arbitrairement partitionnables: propriétés structurelles et algorithmiques, Ph.D. Thesis (Université de Versailles Saint-Quentin, France, 2009).

Close