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

Previous Page 28 Next

Displaying 541 – 560 of 593

Showing per page

Total edge irregularity strength of trees

Jaroslav Ivančo, Stanislav Jendrol' (2006)

Discussiones Mathematicae Graph Theory

A total edge-irregular k-labelling ξ:V(G)∪ E(G) → {1,2,...,k} of a graph G is a labelling of vertices and edges of G in such a way that for any different edges e and f their weights wt(e) and wt(f) are distinct. The weight wt(e) of an edge e = xy is the sum of the labels of vertices x and y and the label of the edge e. The minimum k for which a graph G has a total edge-irregular k-labelling is called the total edge irregularity strength of G, tes(G). In this paper we prove that for every...

Total outer-connected domination in trees

Joanna Cyman (2010)

Discussiones Mathematicae Graph Theory

Let G = (V,E) be a graph. Set D ⊆ V(G) is a total outer-connected dominating set of G if D is a total dominating set in G and G[V(G)-D] is connected. The total outer-connected domination number of G, denoted by γ t c ( G ) , is the smallest cardinality of a total outer-connected dominating set of G. We show that if T is a tree of order n, then γ t c ( T ) ≥ ⎡ 2 n / 3 ⎤ . Moreover, we constructively characterize the family of extremal trees T of order n achieving this lower bound.

Tree compression pushdown automaton

Jan Janoušek, Bořivoj Melichar, Martin Poliak (2012)

Kybernetika

A new kind of a deterministic pushdown automaton, called a Tree Compression Automaton, is presented. The tree compression automaton represents a complete compressed index of a set of trees for subtrees and accepts all subtrees of given trees. The algorithm for constructing our pushdown automaton is incremental. For a single tree with n nodes, the automaton has at most n + 1 states, its transition function cardinality is at most 4 n and there are 2 n + 1 pushdown store symbols. If hashing is used for storing...

Tree-like isometric subgraphs of hypercubes

Bostjan Brešar, Wilfried Imrich, Sandi Klavžar (2003)

Discussiones Mathematicae Graph Theory

Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we shall call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph of a tree-like...

Trees and matchings.

Kenyon, Richard W., Propp, James G., Wilson, David B. (2000)

The Electronic Journal of Combinatorics [electronic only]

Trees with equal 2-domination and 2-independence numbers

Mustapha Chellali, Nacéra Meddah (2012)

Discussiones Mathematicae Graph Theory

Let G = (V,E) be a graph. A subset S of V is a 2-dominating set if every vertex of V-S is dominated at least 2 times, and S is a 2-independent set of G if every vertex of S has at most one neighbor in S. The minimum cardinality of a 2-dominating set a of G is the 2-domination number γ₂(G) and the maximum cardinality of a 2-independent set of G is the 2-independence number β₂(G). Fink and Jacobson proved that γ₂(G) ≤ β₂(G) for every graph G. In this paper we provide a constructive characterization...

Trees with equal restrained domination and total restrained domination numbers

Joanna Raczek (2007)

Discussiones Mathematicae Graph Theory

For a graph G = (V,E), a set D ⊆ V(G) is a total restrained dominating set if it is a dominating set and both ⟨D⟩ and ⟨V(G)-D⟩ do not have isolated vertices. The cardinality of a minimum total restrained dominating set in G is the total restrained domination number. A set D ⊆ V(G) is a restrained dominating set if it is a dominating set and ⟨V(G)-D⟩ does not contain an isolated vertex. The cardinality of a minimum restrained dominating set in G is the restrained domination number. We characterize...

Trees with equal total domination and total restrained domination numbers

Xue-Gang Chen, Wai Chee Shiu, Hong-Yu Chen (2008)

Discussiones Mathematicae Graph Theory

For a graph G = (V,E), a set S ⊆ V(G) is a total dominating set if it is dominating and both ⟨S⟩ has no isolated vertices. The cardinality of a minimum total dominating set in G is the total domination number. A set S ⊆ V(G) is a total restrained dominating set if it is total dominating and ⟨V(G)-S⟩ has no isolated vertices. The cardinality of a minimum total restrained dominating set in G is the total restrained domination number. We characterize all trees for which total domination and total restrained...

Trees with unique minimum total dominating sets

Teresa W. Haynes, Michael A. Henning (2002)

Discussiones Mathematicae Graph Theory

A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. We provide three equivalent conditions for a tree to have a unique minimum total dominating set and give a constructive characterization of such trees.

T-theory.

Dress, Andreas, Moulton, Vincent, Terhalle, Werner (1995)

Séminaire Lotharingien de Combinatoire [electronic only]

Currently displaying 541 – 560 of 593