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 75 Next

Displaying 1481 – 1500 of 5365

Showing per page

Domination parameters of a graph with deleted special subset of edges

Maria Kwaśnik, Maciej Zwierzchowski (2001)

Discussiones Mathematicae Graph Theory

This paper contains a number of estimations of the split domination number and the maximal domination number of a graph with a deleted subset of edges which induces a complete subgraph Kₚ. We discuss noncomplete graphs having or not having hanging vertices. In particular, for p = 2 the edge deleted graphs are considered. The motivation of these problems comes from [2] and [6], where the authors, among other things, gave the lower and upper bounds on irredundance, independence and domination numbers...

Domination Subdivision Numbers

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, David P. Jacobs, James Knisely, Lucas C. van der Merwe (2001)

Discussiones Mathematicae Graph Theory

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number s d γ ( G ) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that 1 ≤ s d γ ( G ) ≤ 3 for any graph G. We give a counterexample to this conjecture. On the other hand, we show...

Domination with respect to nondegenerate and hereditary properties

Vladimir D. Samodivkin (2008)

Mathematica Bohemica

For a graphical property 𝒫 and a graph G , a subset S of vertices of G is a 𝒫 -set if the subgraph induced by S has the property 𝒫 . The domination number with respect to the property 𝒫 , is the minimum cardinality of a dominating 𝒫 -set. In this paper we present results on changing and unchanging of the domination number with respect to the nondegenerate and hereditary properties when a graph is modified by adding an edge or deleting a vertex.

Domination with respect to nondegenerate properties: vertex and edge removal

Vladimir D. Samodivkin (2013)

Mathematica Bohemica

In this paper we present results on changing and unchanging of the domination number with respect to the nondegenerate property 𝒫 , denoted by γ 𝒫 ( G ) , when a graph G is modified by deleting a vertex or deleting edges. A graph G is ( γ 𝒫 ( G ) , k ) 𝒫 -critical if γ 𝒫 ( G - S ) < γ 𝒫 ( G ) for any set S ⊊ V ( G ) with | S | = k . Properties of ( γ 𝒫 , k ) 𝒫 -critical graphs are studied. The plus bondage number with respect to the property 𝒫 , denoted b 𝒫 + ( G ) , is the cardinality of the smallest set of edges U ⊆ E ( G ) such that γ 𝒫 ( G - U ) > γ 𝒫 ( G ) . Some known results for ordinary domination and bondage numbers...

Double domination critical and stable graphs upon vertex removal

Soufiane Khelifi, Mustapha Chellali (2012)

Discussiones Mathematicae Graph Theory

In a graph a vertex is said to dominate itself and all its neighbors. A double dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. The double domination number of G, denoted γ × 2 ( G ) , is the minimum cardinality among all double dominating sets of G. We consider the effects of vertex removal on the double domination number of a graph. A graph G is γ × 2 -vertex critical graph ( γ × 2 -vertex stable graph, respectively) if the removal of any vertex different from a support...

Double geodetic number of a graph

A.P. Santhakumaran, T. Jebaraj (2012)

Discussiones Mathematicae Graph Theory

For a connected graph G of order n, a set S of vertices is called a double geodetic set of G if for each pair of vertices x,y in G there exist vertices u,v ∈ S such that x,y ∈ I[u,v]. The double geodetic number dg(G) is the minimum cardinality of a double geodetic set. Any double godetic of cardinality dg(G) is called dg-set of G. The double geodetic numbers of certain standard graphs are obtained. It is shown that for positive integers r,d such that r < d ≤ 2r and 3 ≤ a ≤ b there exists a connected...

Downhill Domination in Graphs

Teresa W. Haynes, Stephen T. Hedetniemi, Jessie D. Jamieson, William B. Jamieson (2014)

Discussiones Mathematicae Graph Theory

A path π = (v1, v2, . . . , vk+1) in a graph G = (V,E) is a downhill path if for every i, 1 ≤ i ≤ k, deg(vi) ≥ deg(vi+1), where deg(vi) denotes the degree of vertex vi ∈ V. The downhill domination number equals the minimum cardinality of a set S ⊆ V having the property that every vertex v ∈ V lies on a downhill path originating from some vertex in S. We investigate downhill domination numbers of graphs and give upper bounds. In particular, we show that the downhill domination number of a graph is...

Currently displaying 1481 – 1500 of 5365