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

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

Displaying similar documents to “A characterization of roman trees”

On well-covered graphs of odd girth 7 or greater

Bert Randerath, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth...

On integral sum graphs with a saturated vertex

Zhibo Chen (2010)

Czechoslovak Mathematical Journal

Similarity:

As introduced by F. Harary in 1994, a graph G is said to be an i n t e g r a l s u m g r a p h if its vertices can be given a labeling f with distinct integers so that for any two distinct vertices u and v of G , u v is an edge of G if and only if f ( u ) + f ( v ) = f ( w ) for some vertex w in G . We prove that every integral sum graph with a saturated vertex, except the complete graph K 3 , has edge-chromatic number equal to its maximum degree. (A vertex of a graph G is said to be if it is adjacent to every...

Minus total domination in graphs

Hua Ming Xing, Hai-Long Liu (2009)

Czechoslovak Mathematical Journal

Similarity:

A three-valued function f V { - 1 , 0 , 1 } defined on the vertices of a graph G = ( V , E ) is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. That is, for every v V , f ( N ( v ) ) 1 , where N ( v ) consists of every vertex adjacent to v . The weight of an MTDF is f ( V ) = f ( v ) , over all vertices v V . The minus total domination number of a graph G , denoted γ t - ( G ) , equals the minimum weight of an MTDF of G . In this paper, we discuss some properties of minus total domination on a graph...

Restrained domination in unicyclic graphs

Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by γ r ( G ) , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then γ r ( U ) n / 3 , and provide a characterization of graphs achieving this bound.

The cobondage number of a graph

V.R. Kulli, B. Janakiram (1996)

Discussiones Mathematicae Graph Theory

Similarity:

A set D of vertices in a graph G = (V,E) is a dominating set of G if every vertex in V-D is adjacent to some vertex in D. The domination number γ(G) of G is the minimum cardinality of a dominating set. We define the cobondage number b c ( G ) of G to be the minimum cardinality among the sets of edges X ⊆ P₂(V) - E, where P₂(V) = X ⊆ V:|X| = 2 such that γ(G+X) < γ(G). In this paper, the exact values of bc(G) for some standard graphs are found and some bounds are obtained. Also, a Nordhaus-Gaddum...

Uniquely partitionable planar graphs with respect to properties having a forbidden tree

Jozef Bucko, Jaroslav Ivančo (1999)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁, ₂ be graph properties. A vertex (₁,₂)-partition of a graph G is a partition V₁,V₂ of V(G) such that for i = 1,2 the induced subgraph G [ V i ] has the property i . A property ℜ = ₁∘₂ is defined to be the set of all graphs having a vertex (₁,₂)-partition. A graph G ∈ ₁∘₂ is said to be uniquely (₁,₂)-partitionable if G has exactly one vertex (₁,₂)-partition. In this note, we show the existence of uniquely partitionable planar graphs with respect to hereditary additive properties having a...

On total restrained domination in graphs

De-xiang Ma, Xue-Gang Chen, Liang Sun (2005)

Czechoslovak Mathematical Journal

Similarity:

In this paper we initiate the study of total restrained domination in graphs. Let G = ( V , E ) be a graph. A total restrained dominating set is a set S V where every vertex in V - S is adjacent to a vertex in S as well as to another vertex in V - S , and every vertex in S is adjacent to another vertex in S . The total restrained domination number of G , denoted by γ r t ( G ) , is the smallest cardinality of a total restrained dominating set of G . First, some exact values and sharp bounds for γ r t ( G ) are given in Section 2....