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: