Displaying similar documents to “ H -convex graphs”

The forcing convexity number of a graph

Gary Chartrand, Ping Zhang (2001)

Czechoslovak Mathematical Journal

Similarity:

For two vertices u and v of a connected graph G , the set I ( u , v ) consists of all those vertices lying on a u – v geodesic in G . For a set S of vertices of G , the union of all sets I ( u , v ) for u , v ∈ S is denoted by I ( S ) . A set S is a convex set if I ( S ) = S . The convexity number c o n ( G ) of G is the maximum cardinality of a proper convex set of G . A convex set S in G with | S | = c o n ( G ) is called a maximum convex set. A subset T of a maximum convex set S of a connected graph G is called a forcing subset for S if S is the unique maximum...

Graphs with convex domination number close to their order

Joanna Cyman, Magdalena Lemańska, Joanna Raczek (2006)

Discussiones Mathematicae Graph Theory

Similarity:

For a connected graph G = (V,E), a set D ⊆ V(G) is a dominating set of G if every vertex in V(G)-D has at least one neighbour in D. The distance d G ( u , v ) between two vertices u and v is the length of a shortest (u-v) path in G. An (u-v) path of length d G ( u , v ) is called an (u-v)-geodesic. A set X ⊆ V(G) is convex in G if vertices from all (a-b)-geodesics belong to X for any two vertices a,b ∈ X. A set X is a convex dominating set if it is convex and dominating. The convex domination number γ c o n ( G ) of a...

On the minus domination number of graphs

Hailong Liu, Liang Sun (2004)

Czechoslovak Mathematical Journal

Similarity:

Let G = ( V , E ) be a simple graph. A 3 -valued function f V ( G ) → { - 1 , 0 , 1 } is said to be a minus dominating function if for every vertex v ∈ V , f ( N [ v ] ) = ∑ u ∈ N [ v ] f ( u ) ≥ 1 , where N [ v ] is the closed neighborhood of v . The weight of a minus dominating function f on G is f ( V ) = ∑ v ∈ V f ( v ) . The minus domination number of a graph G , denoted by γ - ( G ) , equals the minimum weight of a minus dominating function on G . In this paper, the following two results are obtained. (1) If G is a bipartite graph of order n , then γ - ( G ) ≥ 4 n + 1 - 1 - n . (2) For any negative integer k and any positive integer...

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.

On graphs with a unique minimum hull set

Gary Chartrand, Ping Zhang (2001)

Discussiones Mathematicae Graph Theory

Similarity:

We show that for every integer k ≥ 2 and every k graphs G₁,G₂,...,Gₖ, there exists a hull graph with k hull vertices v₁,v₂,...,vₖ such that link L ( v i ) = G i for 1 ≤ i ≤ k. Moreover, every pair a, b of integers with 2 ≤ a ≤ b is realizable as the hull number and geodetic number (or upper geodetic number) of a hull graph. We also show that every pair a,b of integers with a ≥ 2 and b ≥ 0 is realizable as the hull number and forcing geodetic number of a hull graph.

Remarks on partially square graphs, hamiltonicity and circumference

Hamamache Kheddouci (2001)

Discussiones Mathematicae Graph Theory

Similarity:

Given a graph G, its partially square graph G* is a graph obtained by adding an edge (u,v) for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition N G ( x ) ⊆ N G [ u ] ∪ N G [ v ] , where N G [ x ] = N G ( x ) ∪ x . In the case where G is a claw-free graph, G* is equal to G². We define σ ° ₜ = m i n ∑ x ∈ S d G ( x ) : S i s a n i n d e p e n d e n t s e t i n G * a n d | S | = t . We give for hamiltonicity and circumference new sufficient conditions depending on σ° and we improve some known results.

A note on periodicity of the 2-distance operator

Bohdan Zelinka (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The paper solves one problem by E. Prisner concerning the 2-distance operator T₂. This is an operator on the class C f of all finite undirected graphs. If G is a graph from C f , then T₂(G) is the graph with the same vertex set as G in which two vertices are adjacent if and only if their distance in G is 2. E. Prisner asks whether the periodicity ≥ 3 is possible for T₂. In this paper an affirmative answer is given. A result concerning the periodicity 2 is added.