The dynamics of the forest graph operator

DOI10.7151/DMGT.1901zbMATH Open1350.05144arXiv1601.01041OpenAlexW2963566758MaRDI QIDQ339482FDOQ339482

Thomas Zaslavsky, S. M. Hegde, Venkateshwarlu Deva, S. B. Rao, Suresh Dara

Publication date: 11 November 2016

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: In 1966, Cummins introduced the "tree graph": the tree graph $mathbfT(G)$ of a graph $G$ (possibly infinite) has all its spanning trees as vertices, and distinct such trees correspond to adjacent vertices if they differ in just one edge, i.e., two spanning trees $T_1$ and $T_2$ are adjacent if $T_2=T_1-e+f$ for some edges $ein{T}_1$ and $fotin{T}_1$. The tree graph of a connected graph need not be connected. To obviate this difficulty we define the "forest graph": let $G$ be a labeled graph of order $alpha$, finite or infinite, and let $mathfrakN(G)$ be the set of all labeled maximal forests of $G$. The forest graph of $G$, denoted by $mathbfF(G)$, is the graph with vertex set $mathfrakN(G)$ in which two maximal forests $F_1$, $F_2$ of $G$ form an edge if and only if they differ exactly by one edge, i.e., $F_2=F_1-e+f$ for some edges $ein{F}_1$ and $fotin{F}_1$. Using the theory of cardinal numbers, Zorn's lemma, transfinite induction, the axiom of choice and the well-ordering principle, we determine the $mathbfF$-convergence, $mathbfF$-divergence, $mathbfF$-depth and $mathbfF$-stability of any graph $G$. In particular it is shown that a graph $G$ (finite or infinite) is $mathbfF$-convergent if and only if $G$ has at most one cycle of length 3. The $mathbfF$-stable graphs are precisely $K_3$ and $K_1$. The $mathbfF$-depth of any graph $G$ different from $K_3$ and $K_1$ is finite. We also determine various parameters of $mathbfF(G)$ for an infinite graph $G$, including the number, order, size, and degree of its components.

Full work available at URL: https://arxiv.org/abs/1601.01041

zbMATH Keywords

forest graph operatorgraph dynamics

Mathematics Subject Classification ID

Trees (05C05) Infinite graphs (05C63) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Sharp upper bounds for the number of spanning trees of a graph
• Title not available (Why is that?)
• On connectivities of tree graphs
• Title not available (Why is that?)
• A sharp upper bound for the number of spanning trees of a graph
• The number of spanning trees of a graph
• The number of spanning trees of a graph
• 2-Isomorphic Graphs
• An upper bound for the number of spanning trees of a graph
• The number of spanning forests of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The number of spanning trees of a graph with given matching number
• Title not available (Why is that?)

Cited In (2)

• The dynamics of the line and path graph operators
• Title not available (Why is that?)

This page was built for publication: The dynamics of the forest graph operator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q339482)