Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
A connected graph G with order n ≥ 1 is said to be recursively arbitrarily partitionable (R-AP for short) if either it is isomorphic to K1, or for every sequence (n1, . . . , np) of positive integers summing up to n there exists a partition (V1, . . . , Vp) of V (G) such that each Vi induces a connected R-AP subgraph of G on ni vertices. Since previous investigations, it is believed that a R-AP graph should be “almost traceable” somehow. We first show that the longest path of a R-AP graph on n vertices is not constantly lower than n for every n. This is done by exhibiting a graph family C such that, for every positive constant c ≥ 1, there is a R-AP graph in C that has arbitrary order n and whose longest path has order n−c. We then investigate the largest positive constant c’ < 1 such that every R-AP graph on n vertices has its longest path passing through n • c’ vertices. In particular, we show that c’ ≥ 2/3 . This result holds for R-AP graphs with arbitrary connectivity.
Słowa kluczowe
Czasopismo
Rocznik
Tom
Strony
631--640
Opis fizyczny
Bibliogr. 8 poz., rys., tab.
Twórcy
autor
- Univ. Bordeaux LaBRI, UMR 5800, F-33400 Talence, France
- CNRS LaBRI, UMR 5800, F-33400 Talence, France
Bibliografia
- [1] D. Barth, O. Baudon, J. Puech, Decomposable trees: a polynomial algorithm for tripodes, Discret. Appl. Math. 119 (2002) 3, 205–216.
- [2] D. Barth, H. Fournier, A degree bound on decomposable trees, Discret. Math. 306 (2006) 5, 469–477.
- [3] D. Barth, H. Fournier, R. Ravaux, On the shape of decomposable trees, Discret. Math. 309 (2009), 3882–3887.
- [4] O. Baudon, J. Bensmail, F. Foucaud, M. Pilsniak, Structural properties of recursively partitionable graphs with connectivity 2. Preprint available at: http://hal.archives-ouvertes.fr/hal-00672505.
- [5] O. Baudon, F. Foucaud, J. Przybyło, M. Wozniak, Structure of k-connected arbitrarily partitionable graphs. Preprint available at: http://hal.archives-ouvertes.fr/hal-00690253.
- [6] O. Baudon, F. Gilbert, M. Wozniak, Recursively arbitrarily vertex-decomposable suns, Opuscula Math. 31 (2011) 4, 533–547.
- [7] O. Baudon, F. Gilbert, M. Wozniak, Recursively arbitrarily vertex-decomposable graphs, Opuscula Math. 32 (2012) 4, 689–706.
- [8] A. Marczyk, An ore-type condition for arbitrarily vertex decomposable graphs, Discret. Math. 309 (2009) 11, 3588–3594.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-41e714d8-666d-4f1e-ba3f-44938f6b7e31