On the outer-connected domination in graphs

A set S of vertices of a graph G is an outer-connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraph induced by V?S is connected. The outer-connected domination number $\widetilde{\gamma}_{c}(G)$ is the minimum size of such a set. We prove that if δ(G)≥2 and diam?(G)≤2, then $\widetilde{\gamma}_{c}(G)\le (n+1)/2$ , and we study the behavior of $\widetilde{\gamma}_{c}(G)$ under an edge addition.     

The total domination subdivision number in graphs with no induced 3-cycle and 5-cycle

A set S of vertices of a graph G=(V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number $\mathrm{sd}_{\gamma_{t}}(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 total domination number. Favaron, Karami, Khoeilar and Sheikholeslami (J. Comb. Optim. 20:76–84, 2010a) conjectured that: For any connected graph G of order n≥3, $\mathrm{sd}_{\gamma_{t}}(G)\le \gamma_{t}(G)+1$ . In this paper we use matching to prove this conjecture for graphs with no 3-cycle and 5-cycle. In particular this proves the conjecture for bipartite graphs.     

The adjacent vertex distinguishing total coloring of planar graphs

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices have distinct sets of colors. The minimum number of colors needed for an adjacent vertex distinguishing total coloring of G is denoted by $\chi''_{a}(G)$ . In this paper, we characterize completely the adjacent vertex distinguishing total chromatic number of planar graphs G with large maximum degree Δ by showing that if Δ≥14, then $\varDelta+1\leq \chi''_{a}(G)\leq \varDelta+2$ , and $\chi''_{a}(G)=\varDelta+2$ if and only if G contains two adjacent vertices of maximum degree.     

On the total outer-connected domination in graphs

A set S of vertices of a graph G is a total outer-connected dominating set if every vertex in V(G) is adjacent to some vertex in S and the subgraph induced by V?S is connected. The total outer-connected domination number γ _toc (G) is the minimum size of such a set. We give some properties and bounds for γ _toc in general graphs and in trees. For graphs of order n, diameter 2 and minimum degree at least 3, we show that $\gamma_{toc}(G)\le \frac{2n-2}{3}$ and we determine the extremal graphs.     

(p,q)-total labeling of complete graphs

Given a graph G and positive integers p,q with p≥q, the (p,q)-total number $\lambda_{p,q}^{T}(G)$ of G is the width of the smallest range of integers that suffices to label the vertices and the edges of G such that the labels of any two adjacent vertices are at least q apart, the labels of any two adjacent edges are at least q apart, and the difference between the labels of a vertex and its incident edges is at least p. Havet and Yu (Discrete Math 308:496–513, 2008) first introduced this problem and determined the exact value of $\lambda_{p,1}^{T}(K_{n})$ except for even n with p+5≤n≤6p ²?10p+4. Their proof for showing that $\lambda _{p,1}^{T}(K_{n})\leq n+2p-3$ for odd n has some mistakes. In this paper, we prove that if n is odd, then $\lambda_{p}^{T}(K_{n})\leq n+2p-3$ if p=2, p=3, or $4\lfloor\frac{p}{2}\rfloor+3\leq n\leq4p-1$ . And we extend some results that were given in Havet and Yu (Discrete Math 308:496–513, 2008). Beside these, we give a lower bound for $\lambda_{p,q}^{T}(K_{n})$ under the condition that q<p<2q.     

Signed Roman domination in graphs

In this paper we continue the study of Roman dominating functions in graphs. A signed Roman dominating function (SRDF) on a graph G=(V,E) is a function f:V→{?1,1,2} satisfying the conditions that (i) the sum of its function values over any closed neighborhood is at least one and (ii) for every vertex u for which f(u)=?1 is adjacent to at least one vertex v for which f(v)=2. The weight of a SRDF is the sum of its function values over all vertices. The signed Roman domination number of G is the minimum weight of a SRDF in G. We present various lower and upper bounds on the signed Roman domination number of a graph. Let G be a graph of order n and size m with no isolated vertex. We show that $\gamma _{\mathrm{sR}}(G) \ge\frac{3}{\sqrt{2}} \sqrt{n} - n$ and that γ _sR(G)≥(3n?4m)/2. In both cases, we characterize the graphs achieving equality in these bounds. If G is a bipartite graph of order n, then we show that $\gamma_{\mathrm{sR}}(G) \ge3\sqrt{n+1} - n - 3$ , and we characterize the extremal graphs.     

On metric dimension of permutation graphs

The metric dimension \(\dim (G)\) of a graph \(G\) is the minimum number of vertices such that every vertex of \(G\) is uniquely determined by its vector of distances to the set of chosen vertices. Let \(G_1\) and \(G_2\) be disjoint copies of a graph \(G\) , and let \(\sigma : V(G_1) \rightarrow V(G_2)\) be a permutation. Then, a permutation graph \(G_{\sigma }=(V, E)\) has the vertex set \(V=V(G_1) \cup V(G_2)\) and the edge set \(E=E(G_1) \cup E(G_2) \cup \{uv \mid v=\sigma (u)\}\) . We show that \(2 \le \dim (G_{\sigma }) \le n-1\) for any connected graph \(G\) of order \(n\) at least \(3\) . We give examples showing that neither is there a function \(f\) such that \(\dim (G) for all pairs \((G,\sigma )\) , nor is there a function \(g\) such that \(g(\dim (G))>\dim (G_{\sigma })\) for all pairs \((G, \sigma )\) . Further, we characterize permutation graphs \(G_{\sigma }\) satisfying \(\dim (G_{\sigma })=n-1\) when \(G\) is a complete \(k\) -partite graph, a cycle, or a path on \(n\) vertices.     

On colour-blind distinguishing colour pallets in regular graphs

Consider a graph \(G=(V,E)\) and a colouring of its edges with \(k\) colours. Then every vertex \(v\in V\) is associated with a ‘pallet’ of incident colours together with their frequencies, which sum up to the degree of \(v\) . We say that two vertices have distinct pallets if they differ in frequency of at least one colour. This is always the case if these vertices have distinct degrees. We consider an apparently the worse case, when \(G\) is regular. Suppose further that this coloured graph is being examined by a person who cannot name any given colour, but distinguishes one from another. Could we colour the edges of \(G\) so that a person suffering from such colour-blindness is certain that colour pallets of every two adjacent vertices are distinct? Using the Lopsided Lovász Local Lemma, we prove that it is possible using 15 colours for every \(d\) -regular graph with \(d\ge 960\) .     

Objective functions with redundant domains

Let $(E,{ \mathcal{A}})$ be a set system consisting of a finite collection ${ \mathcal{A}}$ of subsets of a ground set E, and suppose that we have a function ? which maps ${ \mathcal{A}}$ into some set S. Now removing a subset K from E gives a restriction ${ \mathcal{A}}(\bar{K})$ to those sets of ${ \mathcal{A}}$ disjoint from K, and we have a corresponding restriction $\phi|_{\hspace {.02in}{ \mathcal{A}}(\bar{K})}$ of our function ?. If the removal of K does not affect the image set of ?, that is $\mbox {Im}(\phi|_{\hspace {.02in}{ \mathcal{A}}(\bar{X})})=\mbox {Im}(\phi)$ , then we will say that K is a kernel set of ${ \mathcal{A}}$ with respect to ?. Such sets are potentially useful in optimisation problems defined in terms of ?. We will call the set of all subsets of E that are kernel sets with respect to ? a kernel system and denote it by $\mathrm {Ker}_{\phi}({ \mathcal{A}})$ . Motivated by the optimisation theme, we ask which kernel systems are matroids. For instance, if ${ \mathcal{A}}$ is the collection of forests in a graph G with coloured edges and ? counts how many edges of each colour occurs in a forest then $\mathrm {Ker}_{\phi}({ \mathcal{A}})$ is isomorphic to the disjoint sum of the cocycle matroids of the differently coloured subgraphs; on the other hand, if ${ \mathcal{A}}$ is the power set of a set of positive integers, and ? is the function which takes the values 1 and 0 on subsets according to whether they are sum-free or not, then we show that $\mathrm {Ker}_{\phi}({ \mathcal{A}})$ is essentially never a matroid.     

Spanning 3-connected index of graphs

For an integer $s>0$ and for $u,v\in V(G)$ with $u\ne v$ , an $(s;u,v)$ -path-system of G is a subgraph H of G consisting of s internally disjoint (u, v)-paths, and such an H is called a spanning $(s;u,v)$ -path system if $V(H)=V(G)$ . The spanning connectivity $\kappa ^{*}(G)$ of graph G is the largest integer s such that for any integer k with $1\le k \le s$ and for any $u,v\in V(G)$ with $u\ne v$ , G has a spanning ( $k;u,v$ )-path-system. Let G be a simple connected graph that is not a path, a cycle or a $K_{1,3}$ . The spanning k-connected index of G, written $s_{k}(G)$ , is the smallest nonnegative integer m such that $L^m(G)$ is spanning k-connected. Let $l(G)=\max \{m:\,G$ has a divalent path of length m that is not both of length 2 and in a $K_{3}$ }, where a divalent path in G is a path whose interval vertices have degree two in G. In this paper, we prove that $s_{3}(G)\le l(G)+6$ . The key proof to this result is that every connected 3-triangular graph is 2-collapsible.     

Adjacent vertex-distinguishing edge coloring of graphs with maximum degree Δ

An adjacent vertex-distinguishing edge coloring, or avd-coloring, of a graph G is a proper edge coloring of G such that no pair of adjacent vertices meets the same set of colors. Let $\operatorname {mad}(G)$ and Δ(G) denote the maximum average degree and the maximum degree of a graph G, respectively. In this paper, we prove that every graph G with Δ(G)≥5 and $\operatorname{mad}(G) < 3-\frac {2}{\Delta}$ can be avd-colored with Δ(G)+1 colors. This completes a result of Wang and Wang (J. Comb. Optim. 19:471–485, 2010).     

Minimum number of disjoint linear forests covering a planar graph

Graph coloring has interesting real-life applications in optimization, computer science and network design, such as file transferring in a computer network, computation of Hessians matrix and so on. In this paper, we consider one important coloring, linear arboricity, which is an improper edge coloring. Moreover, we study linear arboricity on planar graphs with maximum degree \(\varDelta \ge 7\) . We have proved that the linear arboricity of \(G\) is \(\lceil \frac{\varDelta }{2}\rceil \) , if for each vertex \(v\in V(G)\) , there are two integers \(i_v,j_v\in \{3,4,5,6,7,8\}\) such that any two cycles of length \(i_v\) and \(j_v\) , which contain \(v\) , are not adjacent. Clearly, if \(i_v=i, j_v=j\) for each vertex \(v\in V(G)\) , then we can easily get one corollary: for two fixed integers \(i,j\in \{3,4,5,6,7,8\}\) , if there is no adjacent cycles with length \(i\) and \(j\) in \(G\) , then the linear arboricity of \(G\) is \(\lceil \frac{\varDelta }{2}\rceil \) .     

F_{3}-domination problem of graphs

Given a graph \(G\) and a set \(S\subseteq V(G),\) a vertex \(v\) is said to be \(F_{3}\) -dominated by a vertex \(w\) in \(S\) if either \(v=w,\) or \(v\notin S\) and there exists a vertex \(u\) in \(V(G)-S\) such that \(P:wuv\) is a path in \(G\) . A set \(S\subseteq V(G)\) is an \(F_{3}\) -dominating set of \(G\) if every vertex \(v\) is \(F_{3}\) -dominated by a vertex \(w\) in \(S.\) The \(F_{3}\) -domination number of \(G\) , denoted by \(\gamma _{F_{3}}(G)\) , is the minimum cardinality of an \(F_{3}\) -dominating set of \(G\) . In this paper, we study the \(F_{3}\) -domination of Cartesian product of graphs, and give formulas to compute the \(F_{3}\) -domination number of \(P_{m}\times P_{n}\) and \(P_{m}\times C_{n}\) for special \(m,n.\)      

2-Distance paired-dominating number of graphs

Let \(G=(V,E)\) be a simple graph without isolated vertices. For a positive integer \(k\) , a subset \(D\) of \(V(G)\) is a \(k\) -distance paired-dominating set if each vertex in \(V\setminus {D}\) is within distance \(k\) of a vertex in \(D\) and the subgraph induced by \(D\) contains a perfect matching. In this paper, we give some upper bounds on the 2-distance paired-dominating number in terms of the minimum and maximum degree, girth, and order.     

Graphs with small balanced decomposition numbers

A balanced coloring of a graph \(G\) is an ordered pair \((R,B)\) of disjoint subsets \(R,B \subseteq V(G)\) with \(|R|=|B|\) . The balanced decomposition number  \(f(G)\) of a connected graph \(G\) is the minimum integer \(f\) such that for any balanced coloring \((R,B)\) of \(G\) there is a partition \(\mathcal{P}\) of \(V(G)\) such that \(S\) induces a connected subgraph with \(|S| \le f\) and \(|S \cap R| = |S \cap B|\) for \(S \in \mathcal{P}\) . This paper gives a short proof for the result by Fujita and Liu (2010) that a graph \(G\) of \(n\) vertices has \(f(G)=3\) if and only if \(G\) is \(\lfloor \frac{n}{2} \rfloor \) -connected but is not a complete graph.     

L(p,q)-labeling of sparse graphs

Let p and q be positive integers. An L(p,q)-labeling of a graph G with a span s is a labeling of its vertices by integers between 0 and s such that adjacent vertices of G are labeled using colors at least p apart, and vertices having a common neighbor are labeled using colors at least q apart. We denote by λ _p,q (G) the least integer k such that G has an L(p,q)-labeling with span k. The maximum average degree of a graph G, denoted by $\operatorname {Mad}(G)$ , is the maximum among the average degrees of its subgraphs (i.e. $\operatorname {Mad}(G) = \max\{\frac{2|E(H)|}{|V(H)|} ; H \subseteq G \}$ ). We consider graphs G with $\operatorname {Mad}(G) < \frac{10}{3}$ , 3 and $\frac{14}{5}$ . These sets of graphs contain planar graphs with girth 5, 6 and 7 respectively. We prove in this paper that every graph G with maximum average degree m and maximum degree Δ has:

λ _p,q (G)≤(2q?1)Δ+6p+10q?8 if $m < \frac{10}{3}$ and p≥2q.

λ _p,q (G)≤(2q?1)Δ+4p+14q?9 if $m < \frac{10}{3}$ and 2q>p.

λ _p,q (G)≤(2q?1)Δ+4p+6q?5 if m<3.

λ _p,q (G)≤(2q?1)Δ+4p+4q?4 if $m < \frac{14}{5}$ .

We give also some refined bounds for specific values of p, q, or Δ. By the way we improve results of Lih and Wang (SIAM J. Discrete Math. 17(2):264–275, 2003).     

2-Rainbow domination number of Cartesian products: C_{n}\square C_{3} and C_{n}\square C_{5}

A function \(f:V(G)\rightarrow \mathcal P (\{1,\ldots ,k\})\) is called a \(k\) -rainbow dominating function of \(G\) (for short \(kRDF\) of \(G)\) if \( \bigcup \nolimits _{u\in N(v)}f(u)=\{1,\ldots ,k\},\) for each vertex \( v\in V(G)\) with \(f(v)=\varnothing .\) By \(w(f)\) we mean \(\sum _{v\in V(G)}\left|f(v)\right|\) and we call it the weight of \(f\) in \(G.\) The minimum weight of a \( kRDF\) of \(G\) is called the \(k\) -rainbow domination number of \(G\) and it is denoted by \(\gamma _{rk}(G).\) We investigate the \(2\) -rainbow domination number of Cartesian products of cycles. We give the exact value of the \(2\) -rainbow domination number of \(C_{n}\square C_{3}\) and we give the estimation of this number with respect to \(C_{n}\square C_{5},\) \((n\ge 3).\) Additionally, for \(n=3,4,5,6,\) we show that \(\gamma _{r2}(C_{n}\square C_{5})=2n.\)      

Adjacent vertex distinguishing edge colorings of planar graphs with girth at least five

An adjacent vertex distinguishing edge coloring of a graph \(G\) is a proper edge coloring of \(G\) such that any pair of adjacent vertices admit different sets of colors. The minimum number of colors required for such a coloring of \(G\) is denoted by \(\chi ^{\prime }_{a}(G)\) . In this paper, we prove that if \(G\) is a planar graph with girth at least 5 and \(G\) is not a 5-cycle, then \(\chi ^{\prime }_{a}(G)\le \Delta +2\) , where \(\Delta \) is the maximum degree of \(G\) . This confirms partially a conjecture in Zhang et al. (Appl Math Lett 15:623–626, 2002).     

On the complexity of path problems in properly colored directed graphs

We address the complexity class of several problems related to finding a path in a properly colored directed graph. A properly colored graph is defined as a graph G whose vertex set is partitioned into $\mathcal{X}(G)$ stable subsets, where $\mathcal{X}(G)$ denotes the chromatic number of G. We show that to find a simple path that meets all the colors in a properly colored directed graph is NP-complete, and so are the problems of finding a shortest and longest of such paths between two specific nodes.     

Bandwidth sums of block graphs and cacti

A labeling of a graph G is an injective function f:V(G)→?. The bandwidth sum of a graph G with respect to a labeling f is $B_{s}^{f}(G) = \sum_{uv \in E(G)} |f(u)-f(v)|$ and the bandwidth sum of G is $B_{s}(G) = \min\{B_{s}^{f}(G)\colon f\mbox{ is a labeling of }G\}$ . In this paper, we determine bandwidth sums for some block graphs and cacti.