Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Opuscula Mathematica

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

On locally irregular decompositions of subcubic graphs

Baudon O., Bensmail J., Hocquard H., Senhaji M., Sopena E.

Opuscula Mathematica

2018

Vol. 38, no. 6

795--817

A graph G is locally irregular if every two adjacent vertices of G have different degrees. A locally irregular decomposition of G is a partition E1,.. . , Ek of E(G) such that each G[Ei] is locally irregular. Not all graphs admit locally irregular decompositions, but for those who are decomposable, in that sense, it was conjectured by Baudon, Bensmail, Przybyło and Woźniak that they decompose into at most 3 locally irregular graphs. Towards that conjecture, it was recently proved by Bensmail, Merker and Thomassen that every decomposable graph decomposes into at most 328 locally irregular graphs. We here focus on locally irregular decompositions of subcubic graphs, which form an important family of graphs in this context, as all non-decomposable graphs are subcubic. As a main result, we prove that decomposable subcubic graphs decompose into at most 5 locally irregular graphs, and only at most 4 when the maximum average degree is less than 12/5. We then consider weaker decompositions, where subgraphs can also include regular connected components, and prove the relaxations of the conjecture above for subcubic graphs.

On the longest path in a recursively partitionable graph

Bensmail J.

Opuscula Mathematica

2013

Vol. 33, no. 4

631--640

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.