Geodesic
Reducing graphs by lifting rotations of edges to splittable graphs
Ural mathematical journal, Tome 10 (2024) no. 2, pp. 25-36 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A graph $G$ is splittable if its set of vertices can be represented as the union of a clique and a coclique. We will call a graph $H$ a splittable ancestor of a graph $G$ if the graph $G$ is reducible to the graph $H$ using some sequential lifting rotations of edges and $H$ is a splittable graph. A splittable $r$-ancestor of $G$ we will call its splittable ancestor whose Durfey rank is $r$. Let us set $s = ({1}/{2}) (\mathrm{sum}\,\mathrm{tl}(\lambda) - \mathrm{sum}\,\mathrm{hd}(\lambda))$, where $\mathrm{hd}(\lambda)$ and $\mathrm{tl}(\lambda)$ are the head and the tail of a partition $\lambda$. The main goal of this work is to prove that any graph $G$ of Durfey rank $r$ is reducible by $s$ successive lifting rotations of edges to a splittable $r$-ancestor $H$ and $s$ is the smallest non-negative integer with this property. Note that the degree partition $\mathrm{dpt}(G)$ of the graph $G$ can be obtained from the degree partition $\mathrm{dpt}(H)$ of the splittable $r$-ancestor $H$ using a sequence of $s$ elementary transformations of the first type. The obtained results provide new opportunities for investigating the set of all realizations of a given graphical partition using splittable graphs.
Keywords: Graphical partition, Degree partition, Splittable graph, Rotation of an edge
Mots-clés : Integer partition 
@article{UMJ_2024_10_2_a2,
     author = {Vitaly A. Baransky and Valentin V. Zuev and Tatiana A. Senchonok},
     title = {Reducing graphs by lifting rotations of edges to splittable graphs},
     journal = {Ural mathematical journal},
     pages = {25--36},
     year = {2024},
     volume = {10},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UMJ_2024_10_2_a2/}
}
TY  - JOUR
AU  - Vitaly A. Baransky
AU  - Valentin V. Zuev
AU  - Tatiana A. Senchonok
TI  - Reducing graphs by lifting rotations of edges to splittable graphs
JO  - Ural mathematical journal
PY  - 2024
SP  - 25
EP  - 36
VL  - 10
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UMJ_2024_10_2_a2/
LA  - en
ID  - UMJ_2024_10_2_a2
ER  - 
%0 Journal Article
%A Vitaly A. Baransky
%A Valentin V. Zuev
%A Tatiana A. Senchonok
%T Reducing graphs by lifting rotations of edges to splittable graphs
%J Ural mathematical journal
%D 2024
%P 25-36
%V 10
%N 2
%U http://geodesic.mathdoc.fr/item/UMJ_2024_10_2_a2/
%G en
%F UMJ_2024_10_2_a2
Vitaly A. Baransky; Valentin V. Zuev; Tatiana A. Senchonok. Reducing graphs by lifting rotations of edges to splittable graphs. Ural mathematical journal, Tome 10 (2024) no. 2, pp. 25-36. http://geodesic.mathdoc.fr/item/UMJ_2024_10_2_a2/

[1] Andrews G. E., The Theory of Partitions, Cambridge Univ. Press, Cambridge, 1976, 255 pp. | DOI | MR

[2] Baransky V. A., Senchonok T. A., “Around the Erdös–Gallai criterion”, Ural Math. J., 9:1 (2023), 29–48 | DOI | MR | Zbl

[3] Foldes S., Hammer P. L., “Split graphs”, Proc. of the 8th South-Eastern Conf. on omb.: Graph Theory and Computing, 1977, 311–315 | MR | Zbl

[4] Fulkerson D. R., Hoffman A. J., McAndrew M. H., “Some properties of graphs with multiple edges”, Canad. J. Math., 17 (1965), 166–177 | DOI | MR | Zbl

[5] Hammer P. L., Simeone B., “The splittance of a graph”, Combinatorica, 1 (1981), 275–284 | DOI | MR | Zbl

[6] Mahadev N. V. R., Peled U. N., Threshold Graphs and Related Topics, Annals of Discr. Math., no. 56, North-Holland Publ. Co., Amsterdam, 1995, 542 pp. | MR

[7] Merris R., Graph Theory, J. Wiley Sons Inc., New York, 2001, 256 pp. | DOI | MR | Zbl

[8] Merris R., “Split graphs”, European J. Combin., 24 (2003), 413–430 | DOI | MR | Zbl

[9] Tyshkevich R. I., “Decomposition of graphical sequences and unigraphs”, Discrete Math., 220 (2000), 201–238 | DOI | MR | Zbl