On trees with total domination number equal to edge-vertex domination number plus one

An edge e∈E(G) dominates a vertex v∈V(G) if e is incident with v or e is incident with a vertex adjacent to v. An edge-vertex dominating set of a graph G is a set D of edges of G such that every vertex of G is edge-vertex dominated by an edge of D. The edge-vertex domination number of a graph G is the minimum cardinality of an edge-vertex dominating set of G. A subset D?V(G) is a total dominating set of G if every vertex of G has a neighbor in D. The total domination number of G is the minimum cardinality of a total dominating set of G. We characterize all trees with total domination number equal to edge-vertex domination number plus one.     

Domination Defect in Graphs: Guarding With Fewer Guards

In this paper, we introduce a new graph parameter called the domination defect of a graph. The domination number γ of a graph G is the minimum number of vertices required to dominate the vertices of G. Due to the minimality of γ, if a set of vertices of G has cardinality less than γ then there are vertices of G that are not dominated by that set. The k-domination defect of G is the minimum number of vertices which are left un-dominated by a subset of γ - k vertices of G. We study different bounds on the k-domination defect of a graph G with respect to the domination number, order, degree sequence, graph homomorphisms and the existence of efficient dominating sets. We also characterize the graphs whose domination defect is 1 and find exact values of the domination defect for some particular classes of graphs.     

Restrained Domination in Claw-Free Graphs with Minimum Degree at Least Two

Let G = (V, E) be a graph. A set \({S\subseteq 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 γ _r (G), is the smallest cardinality of a restrained dominating set of G. We will show that if G is claw-free with minimum degree at least two and \({G\notin \{C_{4},C_{5},C_{7},C_{8},C_{11},C_{14},C_{17}\}}\) , then \({\gamma_{r}(G)\leq \frac{2n}{5}.}\)     

A note on the independent domination number versus the domination number in bipartite graphs

Let γ(G) and i(G) be the domination number and the independent domination number of G, respectively. Rad and Volkmann posted a conjecture that i(G)/γ(G) ≤ Δ(G)/2 for any graph G, where Δ(G) is its maximum degree (see N. J. Rad, L. Volkmann (2013)). In this work, we verify the conjecture for bipartite graphs. Several graph classes attaining the extremal bound and graphs containing odd cycles with the ratio larger than Δ(G)/2 are provided as well.     

Proper connection number of bipartite graphs

An edge-colored graph G is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph G, denoted by pc(G), is the smallest number of colors that are needed to color the edges of G in order to make it proper connected. In this paper, we obtain the sharp upper bound for pc(G) of a general bipartite graph G and a series of extremal graphs. Additionally, we give a proper 2-coloring for a connected bipartite graph G having δ(G) ≥ 2 and a dominating cycle or a dominating complete bipartite subgraph, which implies pc(G) = 2. Furthermore, we get that the proper connection number of connected bipartite graphs with δ ≥ 2 and diam(G) ≤ 4 is two.     

Total [1,2]-domination in Graphs

A subset S ? V in a graph G = (V,E) is a total [1, 2]-set if, for every vertex \( \upsilon \in V, 1 \leq\mid N (\upsilon)\cap S\mid\leq \). The minimum cardinality of a total [1, 2]-set of G is called the total [1, 2]-domination number, denoted by γ_t[1,2](^G).We establish two sharp upper bounds on the total [1,2]-domination number of a graph G in terms of its order and minimum degree, and characterize the corresponding extremal graphs achieving these bounds. Moreover, we give some sufficient conditions for a graph without total [1, 2]-set and for a graph with the same total [1, 2]-domination number, [1, 2]-domination number and domination number.     

Improved Upper Bound for Generalized Acyclic Chromatic Number of Graphs

A vertex coloring of a graph G is called r-acyclic if it is a proper vertex coloring such that every cycle D receives at least min{|D|, r} colors. The r-acyclic chromatic number of G is the least number of colors in an r-acyclic coloring of G. We prove that for any number r ≥ 4, the r-acyclic chromatic number of any graph G with maximum degree Δ ≥ 7 and with girth at least (r ? 1)Δ is at most (4r ? 3)Δ.     

A variation of a conjecture due to Erdös and Sós

Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e（G） 〉 1/2（k - 1）n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 ＋ 37/2＋ 14 and every graph G on n vertices with e（G） 〉 1/2 （k- 1）n, we prove that there exists a graph G＇ on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.     

The Local Metric Dimension of Strong Product Graphs

A vertex \(v\in V(G)\) is said to distinguish two vertices \(x,y\in V(G)\) of a nontrivial connected graph G if the distance from v to x is different from the distance from v to y. A set \(S\subset V(G)\) is a local metric generator for G if every two adjacent vertices of G are distinguished by some vertex of S. A local metric generator with the minimum cardinality is called a local metric basis for G and its cardinality, the local metric dimension of G. It is known that the problem of computing the local metric dimension of a graph is NP-Complete. In this paper we study the problem of finding exact values or bounds for the local metric dimension of strong product of graphs.     

Upper Bounds for the Paired-Domination Numbers of Graphs

A set \(S\subseteq V\) is a paired-dominating set if every vertex in \(V{\setminus } S\) has at least one neighbor in S and the subgraph induced by S contains a perfect matching. The paired-domination number of a graph G, denoted by \(\gamma _{pr}(G)\), is the minimum cardinality of a paired-dominating set of G. A conjecture of Goddard and Henning says that if G is not the Petersen graph and is a connected graph of order n with minimum degree \(\delta (G)\ge 3\), then \(\gamma _{pr}(G)\le 4n/7\). In this paper, we confirm this conjecture for k-regular graphs with \(k\ge 4\).     

On Eccentric Connectivity Index of Eccentric Graph of Regular Dendrimer

The eccentric connectivity index \(\xi ^c(G)\) of a connected graph G is defined as \(\xi ^c(G) =\sum _{v \in V(G)}{deg(v) e(v)},\) where deg(v) is the degree of vertex v and e(v) is the eccentricity of v. The eccentric graph, \(G_e\), of a graph G has the same set of vertices as G,  with two vertices u, v adjacent in \(G_e\) if and only if either u is an eccentric vertex of v or v is an eccentric vertex of u. In this paper, we obtain a formula for the eccentric connectivity index of the eccentric graph of a regular dendrimer. We also derive a formula for the eccentric connectivity index for the second iteration of eccentric graph of regular dendrimer.     

On the Ratio Between 2-Domination and Total Outer-Independent Domination Numbers of Trees

A 2-dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)\D has at least two neighbors in D.A total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D,and the set V(G)\D is independent.The 2-domination(total outer-independent domination,respectively)number of a graph G is the minimum cardinality of a 2-dominating(total outer-independent dominating,respectively)set of G.We investigate the ratio between2-domination and total outer-independent domination numbers of trees.     

Edge Roman Domination on Graphs

An edge Roman dominating function of a graph G is a function \(f:E(G) \rightarrow \{0,1,2\}\) satisfying the condition that every edge e with \(f(e)=0\) is adjacent to some edge \(e'\) with \(f(e')=2\). The edge Roman domination number of G, denoted by \(\gamma '_R(G)\), is the minimum weight \(w(f) = \sum _{e\in E(G)} f(e)\) of an edge Roman dominating function f of G. This paper disproves a conjecture of Akbari, Ehsani, Ghajar, Jalaly Khalilabadi and Sadeghian Sadeghabad stating that if G is a graph of maximum degree \(\Delta \) on n vertices, then \(\gamma _R'(G) \le \lceil \frac{\Delta }{\Delta +1} n \rceil \). While the counterexamples having the edge Roman domination numbers \(\frac{2\Delta -2}{2\Delta -1} n\), we prove that \(\frac{2\Delta -2}{2\Delta -1} n + \frac{2}{2\Delta -1}\) is an upper bound for connected graphs. Furthermore, we provide an upper bound for the edge Roman domination number of k-degenerate graphs, which generalizes results of Akbari, Ehsani, Ghajar, Jalaly Khalilabadi and Sadeghian Sadeghabad. We also prove a sharp upper bound for subcubic graphs. In addition, we prove that the edge Roman domination numbers of planar graphs on n vertices is at most \(\frac{6}{7}n\), which confirms a conjecture of Akbari and Qajar. We also show an upper bound for graphs of girth at least five that is 2-cell embeddable in surfaces of small genus. Finally, we prove an upper bound for graphs that do not contain \(K_{2,3}\) as a subdivision, which generalizes a result of Akbari and Qajar on outerplanar graphs.     

On Trees with Double Domination Number Equal to the 2-Outer-Independent Domination Number Plus One

A vertex of a graph is said to dominate itself and all of its neighbors.A double dominating set of a graph G is a set D of vertices of G,such that every vertex of G is dominated by at least two vertices of D.The double domination number of a graph G is the minimum cardinality of a double dominating set of G.For a graph G =(V,E),a subset D V(G) is a 2-dominating set if every vertex of V(G) \ D has at least two neighbors in D,while it is a 2-outer-independent dominating set of G if additionally the set V(G)\D is independent.The 2-outer-independent domination number of G is the minimum cardinality of a 2-outer-independent dominating set of G.This paper characterizes all trees with the double domination number equal to the 2-outer-independent domination number plus one.     

A linear algorithm for the domination number of a series-parallel graph

A vertex u in an undirected graph G = (V, E) is said to dominate all its adjacent vertices and itself. A subset D of V is a dominating set in G if every vertex in G is dominated by a vertex in D, and is a minimum dominating set in G if no other dominating set in G has fewer vertices than D. The domination number of G is the cardinality of a minimum dominating set in G.The problem of determining, for a given positive integer k and an undirected graph G, whether G has a dominating set D in G satisfying ¦D¦ ≤ k, is a well-known NP-complete problem. Cockayne have presented a linear time algorithm for finding a minimum dominating set in a tree. In this paper, we will present a linear time algorithm for finding a minimum dominating set in a series-parallel graph.     

Graphs with small diameter determined by their <Emphasis Type="Italic">D</Emphasis>-spectra

Let G be a connected graph with vertex set V(G) = {v₁, v₂,..., v _n }. The distance matrix D(G) = (d _ij )_n×n is the matrix indexed by the vertices of G, where d _ij denotes the distance between the vertices v _i and v _j . Suppose that λ₁(D) ≥ λ₂(D) ≥... ≥ λ _n (D) are the distance spectrum of G. The graph G is said to be determined by its D-spectrum if with respect to the distance matrix D(G), any graph having the same spectrum as G is isomorphic to G. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined by their D-spectra.     

Order of the smallest counterexample to Gallai’s conjecture

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.     

Rainbow Connection Number and Independence Number of a Graph

A path in an edge-colored graph is called rainbow if any two edges of the path have distinct colors. An edge-colored graph is called rainbow connected if there exists a rainbow path between every two vertices of the graph. For a connected graph G, the minimum number of colors that are needed to make G rainbow connected is called the rainbow connection number of G, denoted by rc(G). In this paper, we investigate the relation between the rainbow connection number and the independence number of a graph. We show that if G is a connected graph without pendant vertices, then \(\mathrm{rc}(G)\le 2\alpha (G)-1\). An example is given showing that the upper bound \(2\alpha (G)-1\) is equal to the diameter of G, and so the upper bound is sharp since the diameter of G is a lower bound of \(\mathrm{rc}(G)\).     

Proof of the bandwidth conjecture of Bollobás and Komlós

In this paper we prove the following conjecture by Bollobás and Komlós: For every γ > 0 and integers r ≥ 1 and Δ, there exists β > 0 with the following property. If G is a sufficiently large graph with n vertices and minimum degree at least ((r ? 1)/r + γ)n and H is an r-chromatic graph with n vertices, bandwidth at most β n and maximum degree at most Δ, then G contains a copy of H.     

Edge clique covering sum of graphs

The edge clique cover sum number (resp. edge clique partition sum number) of a graph G, denoted by scc(G) (resp. scp(G)), is defined as the smallest integer k for which there exists a collection of complete subgraphs of G, covering (resp. partitioning) all edges of G such that the sum of sizes of the cliques is at most k. By definition, scc(G) \({\leqq}\) scp(G). Also, it is known that for every graph G on n vertices, scp(G) \({\leqq n^{2}/2}\). In this paper, among some other results, we improve this bound for scc(G). In particular, we prove that if G is a graph on n vertices with no isolated vertex and the maximum degree of the complement of G is d ? 1, for some integer d, then scc(G) \({\leqq cnd\left\lceil\log \left(({n-1})/(d-1)\right)\right\rceil}\), where c is a constant. Moreover, we conjecture that this bound is best possible up to a constant factor. Using a well-known result by Bollobás on set systems, we prove that this conjecture is true at least for d = 2. Finally, we give an interpretation of this conjecture as an interesting set system problem which can be viewed as a multipartite generalization of Bollobás’ two families theorem.