All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 593

Showing per page

2-placement of (p,q)-trees

Beata Orchel (2003)

Discussiones Mathematicae Graph Theory

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 which...

A characterization of roman trees

Michael A. Henning (2002)

Discussiones Mathematicae Graph Theory

A Roman dominating function (RDF) on a graph G = (V,E) is a function f: V → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of f is w ( f ) = ∑ v ∈ V f ( v ) . The Roman domination number is the minimum weight of an RDF in G. It is known that for every graph G, the Roman domination number of G is bounded above by twice its domination number. Graphs which have Roman domination number equal to twice their domination number are called...

A few remarks on the history of MST-problem

Jaroslav Nešetřil (1997)

Archivum Mathematicum

On the background of Borůvka’s pioneering work we present a survey of the development related to the Minimum Spanning Tree Problem. We also complement the historical paper Graham-Hell [GH] by a few remarks and provide an update of the extensive literature devoted to this problem.

A formula for all minors of the adjacency matrix and an application

R. B. Bapat, A. K. Lal, S. Pati (2014)

Special Matrices

We supply a combinatorial description of any minor of the adjacency matrix of a graph. This description is then used to give a formula for the determinant and inverse of the adjacency matrix, A(G), of a graph G, whenever A(G) is invertible, where G is formed by replacing the edges of a tree by path bundles.

A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs

Yaping Mao, Christopher Melekian, Eddie Cheng (2023)

Czechoslovak Mathematical Journal

For a connected graph G = ( V , E ) and a set S ⊆ V ( G ) with at least two vertices, an S -Steiner tree is a subgraph T = ( V ' , E ' ) of G that is a tree with S ⊆ V ' . If the degree of each vertex of S in T is equal to 1, then T is called a pendant S -Steiner tree. Two S -Steiner trees are internally disjoint if they share no vertices other than S and have no edges in common. For S ⊆ V ( G ) and | S | ≥ 2 , the pendant tree-connectivity τ G ( S ) is the maximum number of internally disjoint pendant S -Steiner trees in G , and for k ≥ 2 , the k -pendant tree-connectivity τ k ( G ) ...

A lower bound for the irredundance number of trees

Michael Poschen, Lutz Volkmann (2006)

Discussiones Mathematicae Graph Theory

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 Lemańska's result. ...

Currently displaying 1 – 20 of 593

Page 1 Next