Displaying similar documents to “Matchings and total domination subdivision number in graphs with few induced 4-cycles”

On arbitrarily vertex decomposable unicyclic graphs with dominating cycle

Sylwia Cichacz, Irmina A. Zioło (2006)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,...,nₖ) of positive integers such that ∑ i = 1 k n i = n , there exists a partition (V₁,...,Vₖ) of vertex set of G such that for every i ∈ 1,...,k the set V i induces a connected subgraph of G on n i vertices. We consider arbitrarily vertex decomposable unicyclic graphs with dominating cycle. We also characterize all such graphs with at most four hanging vertices such that exactly two of them have a common neighbour. ...

Domination in partitioned graphs

Zsolt Tuza, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

Let V₁, V₂ be a partition of the vertex set in a graph G, and let γ i denote the least number of vertices needed in G to dominate V i . We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest...

Distance in stratified graphs

Gary Chartrand, Lisa Hansen, Reza Rashidi, Naveed Sherwani (2000)

Czechoslovak Mathematical Journal

Similarity:

A graph G is stratified if its vertex set is partitioned into classes, called strata. If there are k strata, then G is k -stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color X in a stratified graph G , the X -eccentricity e X ( v ) of a vertex v of G is the distance between v and an X -colored vertex furthest from v . The minimum X -eccentricity among the vertices of G is the X -radius r a d X G of G ...

Inequalities involving independence domination, f -domination, connected and total f -domination numbers

San Ming Zhou (2000)

Czechoslovak Mathematical Journal

Similarity:

Let f be an integer-valued function defined on the vertex set V ( G ) of a graph G . A subset D of V ( G ) is an f -dominating set if each vertex x outside D is adjacent to at least f ( x ) vertices in D . The minimum number of vertices in an f -dominating set is defined to be the f -domination number, denoted by γ f ( G ) . In a similar way one can define the connected and total f -domination numbers γ c , f ( G ) and γ t , f ( G ) . If f ( x ) = 1 for all vertices x , then these are the ordinary domination number, connected domination number and total...

Signed total domination number of a graph

Bohdan Zelinka (2001)

Czechoslovak Mathematical Journal

Similarity:

The signed total domination number of a graph is a certain variant of the domination number. If v is a vertex of a graph G , then N ( v ) is its oper neighbourhood, i.e. the set of all vertices adjacent to v in G . A mapping f : V ( G ) → { - 1 , 1 } , where V ( G ) is the vertex set of G , is called a signed total dominating function (STDF) on G , if ∑ x ∈ N ( v ) f ( x ) ≥ 1 for each v ∈ V ( G ) . The minimum of values ∑ x ∈ V ( G ) f ( x ) , taken over all STDF’s of G , is called the signed total domination number of G and denoted by γ s t ( G ) . A theorem stating lower bounds for γ s t ( G ) is...

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.