Page 1 Next

Displaying 1 – 20 of 43

Showing per page

The B-Domatic Number of a Graph

Odile Favaron (2013)

Discussiones Mathematicae Graph Theory

Besides the classical chromatic and achromatic numbers of a graph related to minimum or minimal vertex partitions into independent sets, the b-chromatic number was introduced in 1998 thanks to an alternative definition of the minimality of such partitions. When independent sets are replaced by dominating sets, the parameters corresponding to the chromatic and achromatic numbers are the domatic and adomatic numbers d(G) and ad(G). We introduce the b-domatic number bd(G) as the counterpart of the...

The bondage number of graphs: good and bad vertices

Vladimir Samodivkin (2008)

Discussiones Mathematicae Graph Theory

The domination number γ(G) of a graph G is the minimum number of vertices in a set D such that every vertex of the graph is either in D or is adjacent to a member of D. Any dominating set D of a graph G with |D| = γ(G) is called a γ-set of G. A vertex x of a graph G is called: (i) γ-good if x belongs to some γ-set and (ii) γ-bad if x belongs to no γ-set. The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination...

The Connectivity Of Domination Dot-Critical Graphs With No Critical Vertices

Michitaka Furuya (2014)

Discussiones Mathematicae Graph Theory

An edge of a graph is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. A vertex of a graph is called critical if its deletion decreases the domination number. In A note on the domination dot-critical graphs, Discrete Appl. Math. 157 (2009) 3743-3745, Chen and Shiu constructed for each even integer k ≥ 4 infinitely many k-dot-critical graphs G with no critical vertices and k(G) = 1. In this paper, we refine...

The diameter of paired-domination vertex critical graphs

Michael A. Henning, Christina M. Mynhardt (2008)

Czechoslovak Mathematical Journal

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G , denoted by γ pr ( G ) , is the minimum cardinality of a paired-dominating set of G . The graph G is paired-domination vertex critical if for every vertex v of G that is not adjacent to a vertex of degree one,...

The Distance Roman Domination Numbers of Graphs

Hamideh Aram, Sepideh Norouzian, Seyed Mahmoud Sheikholeslami (2013)

Discussiones Mathematicae Graph Theory

Let k be a positive integer, and let G be a simple graph with vertex set V (G). A k-distance Roman dominating function on G is a labeling f : V (G) → {0, 1, 2} such that for every vertex with label 0, there is a vertex with label 2 at distance at most k from each other. The weight of a k-distance Roman dominating function f is the value w(f) =∑v∈V f(v). The k-distance Roman domination number of a graph G, denoted by γkR (D), equals the minimum weight of a k-distance Roman dominating function on...

The Domination Number of K 3 n

John Georges, Jianwei Lin, David Mauro (2014)

Discussiones Mathematicae Graph Theory

Let K3n denote the Cartesian product Kn□Kn□Kn, where Kn is the complete graph on n vertices. We show that the domination number of K3n is [...]

The edge C₄ graph of some graph classes

Manju K. Menon, A. Vijayakumar (2010)

Discussiones Mathematicae Graph Theory

The edge C₄ graph of a graph G, E₄(G) is a graph whose vertices are the edges of G and two vertices in E₄(G) are adjacent if the corresponding edges in G are either incident or are opposite edges of some C₄. In this paper, we show that there exist infinitely many pairs of non isomorphic graphs whose edge C₄ graphs are isomorphic. We study the relationship between the diameter, radius and domination number of G and those of E₄(G). It is shown that for any graph G without isolated vertices, there...

The independent resolving number of a graph

Gary Chartrand, Varaporn Saenpholphat, Ping Zhang (2003)

Mathematica Bohemica

For an ordered set W = { w 1 , w 2 , , w k } of vertices in a connected graph G and a vertex v of G , the code of v with respect to W is the k -vector c W ( v ) = ( d ( v , w 1 ) , d ( v , w 2 ) , , d ( v , w k ) ) . The set W is an independent resolving set for G if (1) W is independent in G and (2) distinct vertices have distinct codes with respect to W . The cardinality of a minimum independent resolving set in G is the independent resolving number i r ( G ) . We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs G of order n with i r ( G ) = 1 , n - 1 ,...

The k -domatic number of a graph

Karsten Kämmerling, Lutz Volkmann (2009)

Czechoslovak Mathematical Journal

Let k be a positive integer, and let G be a simple graph with vertex set V ( G ) . A k -dominating set of the graph G is a subset D of V ( G ) such that every vertex of V ( G ) - D is adjacent to at least k vertices in D . A k -domatic partition of G is a partition of V ( G ) into k -dominating sets. The maximum number of dominating sets in a k -domatic partition of G is called the k -domatic number d k ( G ) . In this paper, we present upper and lower bounds for the k -domatic number, and we establish Nordhaus-Gaddum-type results. Some of...

The k-Rainbow Bondage Number of a Digraph

Jafar Amjadi, Negar Mohammadi, Seyed Mahmoud Sheikholeslami, Lutz Volkmann (2015)

Discussiones Mathematicae Graph Theory

Let D = (V,A) be a finite and simple digraph. A k-rainbow dominating function (kRDF) of a digraph D is a function f from the vertex set V to the set of all subsets of the set {1, 2, . . . , k} such that for any vertex v ∈ V with f(v) = Ø the condition ∪u∈N−(v) f(u) = {1, 2, . . . , k} is fulfilled, where N−(v) is the set of in-neighbors of v. The weight of a kRDF f is the value w(f) = ∑v∈V |f(v)|. The k-rainbow domination number of a digraph D, denoted by γrk(D), is the minimum weight of a kRDF...

The k-rainbow domatic number of a graph

Seyyed Mahmoud Sheikholeslami, Lutz Volkmann (2012)

Discussiones Mathematicae Graph Theory

For a positive integer k, a k-rainbow dominating function of a graph G is a function f from the vertex set V(G) to the set of all subsets of the set 1,2, ...,k such that for any vertex v ∈ V(G) with f(v) = ∅ the condition ⋃u ∈ N(v)f(u) = 1,2, ...,k is fulfilled, where N(v) is the neighborhood of v. The 1-rainbow domination is the same as the ordinary domination. A set f , f , . . . , f d of k-rainbow dominating functions on G with the property that i = 1 d | f i ( v ) | k for each v ∈ V(G), is called a k-rainbow dominating family (of...

The maximum clique and the signless Laplacian eigenvalues

Jianping Liu, Bo Lian Liu (2008)

Czechoslovak Mathematical Journal

Lower and upper bounds are obtained for the clique number ω ( G ) and the independence number α ( G ) , in terms of the eigenvalues of the signless Laplacian matrix of a graph G .

Currently displaying 1 – 20 of 43

Page 1 Next