Geodesic
A $\sigma_3$ condition for arbitrarily partitionable graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 755-776 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A graph G of order n is arbitrarily partitionable (AP for short) if, for every partition (λ_1, . . . ,λ_p) of n, there is a partition (V_1, . . . ,V_p) of V(G) such that G[V_i] is a connected graph of order λ_i for every i ∈{1, . . .,p}. Several aspects of AP graphs have been investigated to date, including their connection to Hamiltonian graphs and traceable graphs. Every traceable graph (and, thus, Hamiltonian graph) is indeed known to be AP, and a line of research on AP graphs is thus about weakening, to APness, known sufficient conditions for graphs to be Hamiltonian or traceable. In this work, we provide a sufficient condition for APness involving the parameter σ_3, where, for a given graph G, the parameter σ_3(G) is defined as the minimum value of d(u)+d(v)+d(w)-|N(u) ∩ N(v) ∩ N(w)| for a set {u,v,w} of three pairwise independent vertices u, v, and w of G. Flandrin, Jung, and Li proved that any graph G of order n is Hamitonian provided G is 2-connected and σ_3(G) ≥ n, and traceable provided σ_3(G) ≥ n-1. Unfortunately, we exhibit examples showing that having σ_3(G) ≥ n-2 is not a guarantee for G to be AP. However, we prove that G is AP provided G is 2-connected, σ_3(G) ≥ n-2, and G has a perfect matching or quasi-perfect matching.
Keywords: arbitrarily partitionable graph, partition into connected subgraphs, $\sigma_3$ condition, Hamiltonian graph, traceable graph 
@article{DMGT_2024_44_2_a17,
     author = {Bensmail, Julien},
     title = {A $\sigma_3$ condition for arbitrarily partitionable graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {755--776},
     year = {2024},
     volume = {44},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a17/}
}
TY  - JOUR
AU  - Bensmail, Julien
TI  - A $\sigma_3$ condition for arbitrarily partitionable graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 755
EP  - 776
VL  - 44
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a17/
LA  - en
ID  - DMGT_2024_44_2_a17
ER  - 
%0 Journal Article
%A Bensmail, Julien
%T A $\sigma_3$ condition for arbitrarily partitionable graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 755-776
%V 44
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a17/
%G en
%F DMGT_2024_44_2_a17
Bensmail, Julien. A $\sigma_3$ condition for arbitrarily partitionable graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 755-776. http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a17/

[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] J. Bensmail, Partitions and Decompositions of Graphs, Ph.D. Thesis (Université de Bordeaux, France, 2014).

[3] J. Bensmail and B. Li, More aspects of arbitrarily partitionable graphs, Discuss. Math. Graph Theory 42 (2022) 1237–1261. https://doi.org/10.7151/dmgt.2343

[4] E. Drgas-Burchardt and E. Sidorowicz, Preface, Discuss. Math. Graph Theory 35 (2015) 313–314. https://doi.org/10.7151/dmgt.1809

[5] J. Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965) 449–467. https://doi.org/10.4153/CJM-1965-045-4

[6] E. Flandrin, H. Jung and H. Li, Hamiltonism, degree sum and neighborhood intersections, Discrete Math. 90 (1991) 41–52. https://doi.org/10.1016/0012-365X(91)90094-I

[7] R.J. Gould, Recent advances on the Hamiltonian problem: Survey III}, Graphs Combin. 30 (2014) 1–46. https://doi.org/10.1007/s00373-013-1377-x

[8] E. Győri, On division of graphs to connected subgraphs, in: Proc. 5th Hungarian Combinational Colloquium (1978) 485–494.

[9] 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

[10] M. Horňák and M. Woźniak, Arbitrarily vertex decomposable trees are of degree at most 6, Opuscula Math. 23 (2003) 49–62.

[11] 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

[12] L. Lovász, A homology theory for spanning trees of a graph, Acta Math. Acad. Sci. Hungar. 30 (1977) 241–251.

[13] A. Marczyk, A note on arbitrarily vertex decomposable graphs, Opuscula Math. 26 (2006) 109–118.

[14] 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

[15] B. Momege, Sufficient conditions for a connected graph to have a Hamiltonian path, in: Proceedings of the 2017 International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2017), B. Steffen, C. Baier, M. van den Brand, J. Eder, M. Hinchey and T. Mengaria (Ed(s)), (Theory and Practise of Computer Science, LNCS 10139 2017) 205–216. https://doi.org/10.1007/978-3-319-51963-0_16

[16] O. Ore, Note on hamilton circuits, Amer. Math. Monthly 67 (1960) 55.

[17] R. Ravaux, Decomposing trees with large diameter, Theoret. Comput. Sci. 411 (2010) 3068–3072. https://doi.org/10.1016/j.tcs.2010.04.032

[18] Z. Tian, Pancyclicity in Hamiltonian Graph Theory, Ph.D. Thesis (Université Paris-Saclay, France, 2021).