Displaying similar documents to “On a problem concerning k -subdomination numbers of graphs”

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...

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...

A note on the independent domination number of subset graph

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

Czechoslovak Mathematical Journal

Similarity:

The independent domination number i ( G ) (independent number β ( G ) ) is the minimum (maximum) cardinality among all maximal independent sets of G . Haviland (1995) conjectured that any connected regular graph G of order n and degree δ ≤ 1 2 n satisfies i ( G ) ≤ ⌈ 2 n 3 δ ⌉ 1 2 δ . For 1 ≤ k ≤ l ≤ m , the subset graph S m ( k , l ) is the bipartite graph whose vertices are the k - and l -subsets of an m element ground set where two vertices are adjacent if and only if one subset is contained in the other. In this paper, we give a sharp upper bound for i ( S m ( k , l ) ) and...

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.

A remark on the (2,2)-domination number

Torsten Korneffel, Dirk Meierling, Lutz Volkmann (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A subset D of the vertex set of a graph G is a (k,p)-dominating set if every vertex v ∈ V(G)∖D is within distance k to at least p vertices in D. The parameter γ k , p ( G ) denotes the minimum cardinality of a (k,p)-dominating set of G. In 1994, Bean, Henning and Swart posed the conjecture that γ k , p ( G ) ≤ ( p / ( p + k ) ) n ( G ) for any graph G with δₖ(G) ≥ k+p-1, where the latter means that every vertex is within distance k to at least k+p-1 vertices other than itself. In 2005, Fischermann and Volkmann confirmed this conjecture...

Order of the smallest counterexample to Gallai's conjecture

Fuyuan Chen (2018)

Czechoslovak Mathematical Journal

Similarity:

In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Zamfirescu conjectured that the smallest counterexample to Gallai’s conjecture is a graph on 12 vertices. We prove that Gallai’s conjecture is true for every connected graph G with α ' ( G ) ≤ 5 , which implies that Zamfirescu’s conjecture is true.