The dynamics of the forest graph operator

DOI10.7151/DMGT.1901MaRDI QIDQ339482zbMATH OpenOpenAlexFDO

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

Publication date 11 November 2016

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

forest graph operator graph dynamics

Mathematics Subject Classification ID

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

Abstract: In 1966, Cummins introduced the "tree graph": the tree graph

m a t h b f T (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

e i n T_{1}

and

f o t i n 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

a l p h a

, finite or infinite, and let

m a t h f r a k N (G)

be the set of all labeled maximal forests of

G

. The forest graph of

G

, denoted by

m a t h b f F (G)

, is the graph with vertex set

m a t h f r a k N (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

e i n F_{1}

and

f o t i n 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

m a t h b f F

-convergence,

m a t h b f F

-divergence,

m a t h b f F

-depth and

m a t h b f F

-stability of any graph

G

. In particular it is shown that a graph

G

(finite or infinite) is

m a t h b f F

-convergent if and only if

G

has at most one cycle of length 3. The

m a t h b f F

-stable graphs are precisely

K_{3}

and

K_{1}

. The

m a t h b f F

-depth of any graph

G

different from

K_{3}

and

K_{1}

is finite. We also determine various parameters of

m a t h b f F (G)

for an infinite graph

G

, including the number, order, size, and degree of its components.

Recommendations

Cites work

Cited in

(2)

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)