The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Spanning tree congestion of rook's graphs”

2-placement of (p,q)-trees

Beata Orchel (2003)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (L,R;E) be a bipartite graph such that V(G) = L∪R, |L| = p and |R| = q. G is called (p,q)-tree if G is connected and |E(G)| = p+q-1. Let G = (L,R;E) and H = (L',R';E') be two (p,q)-tree. A bijection f:L ∪ R → L' ∪ R' is said to be a biplacement of G and H if f(L) = L' and f(x)f(y) ∉ E' for every edge xy of G. A biplacement of G and its copy is called 2-placement of G. A bipartite graph G is 2-placeable if G has a 2-placement. In this paper we give all (p,q)-trees...

End-faithful spanning trees of countable graphs with prescribed sets of rays

Norbert Polat (2001)

Czechoslovak Mathematical Journal

Similarity:

We prove that a countable connected graph has an end-faithful spanning tree that contains a prescribed set of rays whenever this set is countable, and we show that this solution is, in a certain sense, the best possible. This improves a result of Hahn and Širáň Theorem 1.

A lower bound for the irredundance number of trees

Michael Poschen, Lutz Volkmann (2006)

Discussiones Mathematicae Graph Theory

Similarity:

Let ir(G) and γ(G) be the irredundance number and domination number of a graph G, respectively. The number of vertices and leaves of a graph G are denoted by n(G) and n₁(G). If T is a tree, then Lemańska [4] presented in 2004 the sharp lower bound γ(T) ≥ (n(T) + 2 - n₁(T))/3. In this paper we prove ir(T) ≥ (n(T) + 2 - n₁(T))/3. for an arbitrary tree T. Since γ(T) ≥ ir(T) is always valid, this inequality is an extension and improvement of...

Completely Independent Spanning Trees in (Partial) k-Trees

Masayoshi Matsushita, Yota Otachi, Toru Araki (2015)

Discussiones Mathematicae Graph Theory

Similarity:

Two spanning trees T1 and T2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T1 and T2 are internally disjoint. For a graph G, we denote the maximum number of pairwise completely independent spanning trees by cist(G). In this paper, we consider cist(G) when G is a partial k-tree. First we show that [k/2] ≤ cist(G) ≤ k − 1 for any k-tree G. Then we show that for any p ∈ {[k/2], . . . , k − 1}, there exist infinitely many k-trees G such...

On the tree graph of a connected graph

Ana Paulina Figueroa, Eduardo Rivera-Campo (2008)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph and C be a set of cycles of G. The tree graph of G defined by C, is the graph T(G,C) that has one vertex for each spanning tree of G, in which two trees T and T' are adjacent if their symmetric difference consists of two edges and the unique cycle contained in T ∪ T' is an element of C. We give a necessary and sufficient condition for this graph to be connected for the case where every edge of G belongs to at most two cycles in C.

A note on domino treewidth.

Bodlaender, Hans L. (1999)

Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]

Similarity:

A characterization of (γₜ,γ₂)-trees

You Lu, Xinmin Hou, Jun-Ming Xu, Ning Li (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Let γₜ(G) and γ₂(G) be the total domination number and the 2-domination number of a graph G, respectively. It has been shown that: γₜ(T) ≤ γ₂(T) for any tree T. In this paper, we provide a constructive characterization of those trees with equal total domination number and 2-domination number.