Wiener and vertex PI indices of the strong product of graphs

K. Pattabiraman; P. Paulraja

Displaying similar documents to “Wiener and vertex PI indices of the strong product of graphs”

The Wiener number of powers of the Mycielskian

Rangaswami Balakrishnan, S. Francis Raj (2010)

Discussiones Mathematicae Graph Theory

Similarity:

The Wiener number of a graph G is defined as $1 / 2 \sum_{u, v \in V (G)} d (u, v)$ , d the distance function on G. The Wiener number has important applications in chemistry. We determine a formula for the Wiener number of an important graph family, namely, the Mycielskians μ(G) of graphs G. Using this, we show that for k ≥ 1, $W (μ (S ₙ^{k})) \leq W (μ (T ₙ^{k})) \leq W (μ (P ₙ^{k}))$ , where Sₙ, Tₙ and Pₙ denote a star, a general tree and a path on n vertices respectively. We also obtain Nordhaus-Gaddum type inequality for the Wiener number of $μ (G^{k})$ .

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

Similarity:

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 \leq s d_{γ} (G) \leq 3$ for any graph G. We give a counterexample to this conjecture. On the other hand,...

Domination and independence subdivision numbers of graphs

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The domination subdivision number $s d_{γ} (G)$ of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of...

On the order of certain close to regular graphs without a matching of given size

Sabine Klinkenberg, Lutz Volkmann (2007)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is a ${d, d + k}$ -graph, if one vertex has degree $d + k$ and the remaining vertices of $G$ have degree $d$ . In the special case of $k = 0$ , the graph $G$ is $d$ -regular. Let $k, p \geq 0$ and $d, n \geq 1$ be integers such that $n$ and $p$ are of the same parity. If $G$ is a connected ${d, d + k}$ -graph of order $n$ without a matching $M$ of size $2 | M | = n - p$ , then we show in this paper the following: If $d = 2$ , then $k \geq 2 (p + 2)$ and (i) $n \geq k + p + 6$ . If $d \geq 3$ is odd and $t$ an integer with $1 \leq t \leq p + 2$ , then (ii) $n \geq d + k + 1$ for $k \geq d (p + 2)$ , (iii) $n \geq d (p + 3) + 2 t + 1$ for $d (p + 2 - t) + t \leq k \leq d (p + 3 - t) + t - 3$ , (iv) $n \geq d (p + 3) + 2 p + 7$ for $k \leq p$ . If $d \geq 4$ is even, then (v) $n \geq d + k + 2 - η$ for $k \geq d (p + 3) + p + 4 + η$ , (vi) $n \geq d + k + p + 2 - 2 t = d (p + 4) + p + 6$ for $k = d (p + 3) + 4 + 2 t$ and $p \geq 1$ ,...

Roman bondage in graphs

Nader Jafari Rad, Lutz Volkmann (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A Roman dominating function on a graph G is a function f:V(G) → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the value $f (V (G)) = \sum_{u \in V (G)} f (u)$ . The Roman domination number, $γ_{R} (G)$ , of G is the minimum weight of a Roman dominating function on G. In this paper, we define the Roman bondage $b_{R} (G)$ of a graph G with maximum degree at least two to be the minimum cardinality of all sets E’ ⊆ E(G)...

Full domination in graphs

Robert C. Brigham, Gary Chartrand, Ronald D. Dutton, Ping Zhang (2001)

Discussiones Mathematicae Graph Theory

Similarity:

For each vertex v in a graph G, let there be associated a subgraph $H_{v}$ of G. The vertex v is said to dominate $H_{v}$ as well as dominate each vertex and edge of $H_{v}$ . A set S of vertices of G is called a full dominating set if every vertex of G is dominated by some vertex of S, as is every edge of G. The minimum cardinality of a full dominating set of G is its full domination number $γ_{F H} (G)$ . A full dominating set of G of cardinality $γ_{F H} (G)$ is called a $γ_{F H}$ -set of G. We study three types of full domination in...

On the total k-domination number of graphs

Adel P. Kazemi (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let k be a positive integer and let G = (V,E) be a simple graph. The k-tuple domination number $γ_{\times k} (G)$ of G is the minimum cardinality of a k-tuple dominating set S, a set that for every vertex v ∈ V, $| N_{G} [v] \cap S | \geq k$ . Also the total k-domination number $γ_{\times k, t} (G)$ of G is the minimum cardinality of a total k -dominating set S, a set that for every vertex v ∈ V, $| N_{G} (v) \cap S | \geq k$ . The k-transversal number τₖ(H) of a hypergraph H is the minimum size of a subset S ⊆ V(H) such that |S ∩e | ≥ k for every edge e ∈ E(H). We know that for...

The geodetic number of strong product graphs

A.P. Santhakumaran, S.V. Ullas Chandran (2010)

Discussiones Mathematicae Graph Theory

Similarity:

For two vertices u and v of a connected graph G, the set $I_{G} [u, v]$ consists of all those vertices lying on u-v geodesics in G. Given a set S of vertices of G, the union of all sets $I_{G} [u, v]$ for u,v ∈ S is denoted by $I_{G} [S]$ . A set S ⊆ V(G) is a geodetic set if $I_{G} [S] = V (G)$ and the minimum cardinality of a geodetic set is its geodetic number g(G) of G. Bounds for the geodetic number of strong product graphs are obtainted and for several classes improved bounds and exact values are obtained.

The vertex detour hull number of a graph

A.P. Santhakumaran, S.V. Ullas Chandran (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For vertices x and y in a connected graph G, the detour distance D(x,y) is the length of a longest x - y path in G. An x - y path of length D(x,y) is an x - y detour. The closed detour interval ID[x,y] consists of x,y, and all vertices lying on some x -y detour of G; while for S ⊆ V(G), $I_{D} [S] = ⋃_{x, y \in S} I_{D} [x, y]$ . A set S of vertices is a detour convex set if $I_{D} [S] = S$ . The detour convex hull ${[S]}_{D}$ is the smallest detour convex set containing S. The detour hull number dh(G) is the minimum cardinality among subsets S of...

On locating-domination in graphs

Mustapha Chellali, Malika Mimouni, Peter J. Slater (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A set D of vertices in a graph G = (V,E) is a locating-dominating set (LDS) if for every two vertices u,v of V-D the sets N(u)∩ D and N(v)∩ D are non-empty and different. The locating-domination number $γ_{L} (G)$ is the minimum cardinality of a LDS of G, and the upper locating-domination number, $Γ_{L} (G)$ is the maximum cardinality of a minimal LDS of G. We present different bounds on $Γ_{L} (G)$ and $γ_{L} (G)$ .

Stronger bounds for generalized degrees and Menger path systems

R.J. Faudree, Zs. Tuza (1995)

Discussiones Mathematicae Graph Theory

Similarity:

For positive integers d and m, let $P_{d, m} (G)$ denote the property that between each pair of vertices of the graph G, there are m internally vertex disjoint paths of length at most d. For a positive integer t a graph G satisfies the minimum generalized degree condition δₜ(G) ≥ s if the cardinality of the union of the neighborhoods of each set of t vertices of G is at least s. Generalized degree conditions that ensure that $P_{d, m} (G)$ is satisfied have been investigated. In particular, it has been shown,...

On double domination in graphs

Jochen Harant, Michael A. Henning (2005)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number $γ_{\times 2} (G)$ . A function f(p) is defined, and it is shown that $γ_{\times 2} (G) = m i n f (p)$ , where the minimum is taken over the n-dimensional cube $C ⁿ = p = (p ₁, . . ., p ₙ) | p_{i} \in I R, 0 \leq p_{i} \leq 1, i = 1, . . ., n$ . Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then $γ_{\times 2} (G) \leq ((l n (1 + d) + l n δ + 1) / δ) n$ .

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.

On the adjacent eccentric distance sum of graphs

Halina Bielak, Katarzyna Wolska (2014)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

In this paper we show bounds for the adjacent eccentric distance sum of graphs in terms of Wiener index, maximum degree and minimum degree. We extend some earlier results of Hua and Yu [Bounds for the Adjacent Eccentric Distance Sum, International Mathematical Forum, Vol. 7 (2002) no. 26, 1289–1294]. The adjacent eccentric distance sum index of the graph $G$ is defined as $ξ^{s v} (G) = \sum_{v \in V (G)} \frac{ε (v) D (v)}{d e g (v)},$ where $ε (v)$ is the eccentricity of the vertex $v$ , $d e g (v)$ is the degree of the vertex $v$ and $D (v) = \sum_{u \in V (G)} d (u, v)$ is the sum of all distances from...

Paired domination in prisms of graphs

Christina M. Mynhardt, Mark Schurch (2011)

Discussiones Mathematicae Graph Theory

Similarity:

The paired domination number $γ_{p r} (G)$ of a graph G is the smallest cardinality of a dominating set S of G such that ⟨S⟩ has a perfect matching. The generalized prisms πG of G are the graphs obtained by joining the vertices of two disjoint copies of G by |V(G)| independent edges. We provide characterizations of the following three classes of graphs: $γ_{p r} (π G) = 2 γ_{p r} (G)$ for all πG; $γ_{p r} (K ₂ ☐ G) = 2 γ_{p r} (G)$ ; $γ_{p r} (K ₂ ☐ G) = γ_{p r} (G)$ .

On 𝓕-independence in graphs

Frank Göring, Jochen Harant, Dieter Rautenbach, Ingo Schiermeyer (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let be a set of graphs and for a graph G let $α_{} (G)$ and $α *_{} (G)$ denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on $α_{} (G)$ and $α *_{} (G)$ are presented.

On the diameter of the intersection graph of a finite simple group

Xuanlong Ma (2016)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a finite group. The intersection graph $Δ_{G}$ of $G$ is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper nontrivial subgroups of $G$ , and two distinct vertices $X$ and $Y$ are adjacent if $X \cap Y \neq 1$ , where $1$ denotes the trivial subgroup of order $1$ . A question was posed by Shen (2010) whether the diameters of intersection graphs of finite non-abelian simple groups have an upper bound. We answer the question and show that the diameters...

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) \leq (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...