Restrained bondage in graphs

Let $G=(V,E)$ be a graph. A set $S?V$ is a restrained dominating set if every vertex not in $S$ is adjacent to a vertex in $S$ and to a vertex in $V?S$. The restrained domination number of $G$, denoted by ${\gamma }_r\left(G\right)$, is the smallest cardinality of a restrained dominating set of $G$. We define the restrained bondage number $b_r\left(G\right)$ of a nonempty graph $G$ to be the minimum cardinality among all sets of edges $E^{\prime }?E$ for which ${\gamma }_r(G?E^{\prime })>{\gamma }_r\left(G\right)$. Sharp bounds are obtained for $b_r\left(G\right)$, and exact values are determined for several classes of graphs. Also, we show that the decision problem for $b_r\left(G\right)$ is NP-complete even for bipartite graphs.     

Steiner tree packing number and tree connectivity

Let $S$ be a set of at least two vertices in a graph $G$. A subtree $T$ of $G$ is a $S$-Steiner tree if $S?V\left(T\right)$. Two $S$-Steiner trees $T_1$ and $T_2$ are edge-disjoint (resp. internally vertex-disjoint) if $E\left(T_1\right)\cap E\left(T_2\right)=?$ (resp. $E\left(T_1\right)\cap E\left(T_2\right)=?$ and $V\left(T_1\right)\cap V\left(T_2\right)=S$). Let ${\lambda }_G\left(S\right)$ (resp. ${\kappa }_G\left(S\right)$) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) $S$-Steiner trees in $G$, and let ${\lambda }_k\left(G\right)$ (resp. ${\kappa }_k\left(G\right)$) be the minimum ${\lambda }_G\left(S\right)$ (resp. ${\kappa }_G\left(S\right)$) for $S$ ranges over all $k$-subset of $V\left(G\right)$. Kriesell conjectured that if ${\lambda }_G\left(\{x,y\}\right)\ge 2k$ for any $x,y\in S$, then ${\lambda }_G\left(S\right)\ge k$. He proved that the conjecture holds for $\left|S\right|=3,4$. In this paper, we give a short proof of Kriesell’s Conjecture for $\left|S\right|=3,4$, and also show that ${\lambda }_k\left(G\right)\ge ?\frac{1}{k?1}?\frac{k?}{2}??$ (resp. ${\kappa }_k\left(G\right)\ge ?\frac{1}{k?1}?\frac{k?}{2}??$ ) if $\lambda \left(G\right)\ge ?$ (resp. $\kappa \left(G\right)\ge ?$) in $G$, where $k=3,4$. Moreover, we also study the relation between ${\kappa }_k\left(L\left(G\right)\right)$ and ${\lambda }_k\left(G\right)$, where $L\left(G\right)$ is the line graph of $G$.     

On graphs with largest possible game domination number

Let $\gamma \left(G\right)$ and ${\gamma }_g\left(G\right)$ be the domination number and the game domination number of a graph $G$, respectively. In this paper ${\gamma }_g$-maximal graphs are introduced as the graphs $G$ for which ${\gamma }_g\left(G\right)=2\gamma \left(G\right)?1$ holds. Large families of ${\gamma }_g$-maximal graphs are constructed among the graphs in which their sets of support vertices are minimum dominating sets. ${\gamma }_g$-maximal graphs are also characterized among the starlike trees, that is, trees which have exactly one vertex of degree at least $3$.     

Total domination in inflated graphs

The inflation $G_I$ of a graph $G$ is obtained from $G$ by replacing every vertex $x$ of degree $d\left(x\right)$ by a clique $X=K_{d\left(x\right)}$ and each edge $xy$ by an edge between two vertices of the corresponding cliques $X$ and $Y$ of $G_I$ in such a way that the edges of $G_I$ which come from the edges of $G$ form a matching of $G_I$. A set $S$ of vertices in a graph $G$ is a total dominating set, abbreviated TDS, of $G$ if every vertex of $G$ is adjacent to a vertex in $S$. The minimum cardinality of a TDS of $G$ is the total domination number ${\gamma }_t\left(G\right)$ of $G$. In this paper, we investigate total domination in inflated graphs. We provide an upper bound on the total domination number of an inflated graph in terms of its order and matching number. We show that if $G$ is a connected graph of order $n\ge 2$, then ${\gamma }_t\left(G_I\right)\ge 2n/3$, and we characterize the graphs achieving equality in this bound. Further, if we restrict the minimum degree of $G$ to be at least $2$, then we show that ${\gamma }_t\left(G_I\right)\ge n$, with equality if and only if $G$ has a perfect matching. If we increase the minimum degree requirement of $G$ to be at least $3$, then we show ${\gamma }_t\left(G_I\right)\ge n$, with equality if and only if every minimum TDS of $G_I$ is a perfect total dominating set of $G_I$, where a perfect total dominating set is a TDS with the property that every vertex is adjacent to precisely one vertex of the set.     

Exponential independence

For a set $S$ of vertices of a graph $G$, a vertex $u$ in $V\left(G\right)?S$, and a vertex $v$ in $S$, let ${\mathrm{dist}}_{(G,S)}(u,v)$ be the distance of $u$ and $v$ in the graph $G?(S?\left\{v\right\})$. Dankelmann et al. (2009) define $S$ to be an exponential dominating set of $G$ if $w_{(G,S)}\left(u\right)\ge 1$ for every vertex $u$ in $V\left(G\right)?S$, where $w_{(G,S)}\left(u\right)={\sum }_{v\in S}{\left(\frac{1}{2}\right)}^{{\mathrm{dist}}_{(G,S)}(u,v)?1}$. Inspired by this notion, we define $S$ to be an exponential independent set of $G$ if $w_{(G,S?\left\{u\right\})}\left(u\right)<1$ for every vertex $u$ in $S$, and the exponential independence number ${\alpha }_e\left(G\right)$ of $G$ as the maximum order of an exponential independent set of $G$.Similarly as for exponential domination, the non-local nature of exponential independence leads to many interesting effects and challenges. Our results comprise exact values for special graphs as well as tight bounds and the corresponding extremal graphs. Furthermore, we characterize all graphs $G$ for which ${\alpha }_e\left(H\right)$ equals the independence number $\alpha \left(H\right)$ for every induced subgraph $H$ of $G$, and we give an explicit characterization of all trees $T$ with ${\alpha }_e\left(T\right)=\alpha \left(T\right)$.     

Kirchhoff index in line,subdivision and total graphs of a regular graph

Let $G$ be a connected regular graph and $l\left(G\right)$, $s\left(G\right)$, $t\left(G\right)$ the line, subdivision, total graphs of $G$, respectively. In this paper, we derive formulae and lower bounds of the Kirchhoff index of $l\left(G\right)$, $s\left(G\right)$ and $t\left(G\right)$, respectively. In particular, we give special formulae for the Kirchhoff index of $l\left(G\right)$, $s\left(G\right)$ and $t\left(G\right)$, where $G$ is a complete graph $K_n$, a regular complete bipartite graph $K_{n,n}$ and a cycle $C_n$.     

Combinatorial and probabilistic formulae for divided symmetrization

Divided symmetrization of a function $f(x_1,\dots ,x_n)$ is symmetrization of the ratio

$D{S}_G\left(f\right)=\frac{f(x_1,\dots ,x_n)}{\prod (x_i?x_j)},$

where the product is taken over the set of edges of some graph $G$. We concentrate on the case when $G$ is a tree and $f$ is a polynomial of degree $n?1$, in this case $D{S}_G\left(f\right)$ is a constant function. We give a combinatorial interpretation of the divided symmetrization of monomials for general trees and probabilistic game interpretation for a tree which is a path. In particular, this implies a result by Postnikov originally proved by computing volumes of special polytopes, and suggests its generalization.     

List colouring of graphs and generalized Dyck paths

The Catalan numbers occur in various counting problems in combinatorics. This paper reveals a connection between the Catalan numbers and list colouring of graphs. Assume $G$ is a graph and $f:V\left(G\right)\to N$ is a mapping. For a nonnegative integer $m$, let $f^{\left(m\right)}$ be the extension of $f$ to the graph $G$

 $\overline{K_m}$ for which $f^{\left(m\right)}\left(v\right)=\left|V\left(G\right)\right|$ for each vertex $v$ of $\overline{K_m}$. Let $m_c(G,f)$ be the minimum $m$ such that $G$

 $\overline{K_m}$ is not $f^{\left(m\right)}$-choosable and $m_p(G,f)$ be the minimum $m$ such that $G$

 $\overline{K_m}$ is not $f^{\left(m\right)}$-paintable. We study the parameter $m_c(K_n,f)$ and $m_p(K_n,f)$ for arbitrary mappings $f$. For $\overrightarrow{x}=(x_1,x_2,\dots ,x_n)$, an $\overrightarrow{x}$-dominated path ending at $(a,b)$ is a monotonic path $P$ of the $a\times b$ grid from $(0,0)$ to $(a,b)$ such that each vertex $(i,j)$ on $P$ satisfies $i\le x_{j+1}$. Let $\psi \left(\overrightarrow{x}\right)$ be the number of $\overrightarrow{x}$-dominated paths ending at $(x_n,n)$. By this definition, the Catalan number $C_n$ equals $\psi \left((0,1,\dots ,n?1)\right)$. This paper proves that if $G=K_n$ has vertices $v_1,v_2,\dots ,v_n$ and $f\left(v_1\right)\le f\left(v_2\right)\le \dots \le f\left(v_n\right)$, then $m_c(G,f)=m_p(G,f)=\psi \left(\overrightarrow{x}\left(f\right)\right)$, where $\overrightarrow{x}\left(f\right)=(x_1,x_2,\dots ,x_n)$ and $x_i=f\left(v_i\right)?i$ for $i=1,2,\dots ,n$. Therefore, if $f\left(v_i\right)=n$, then $m_c(K_n,f)=m_p(K_n,f)$ equals the Catalan number $C_n$. We also show that if $G=G_1\cup G_2\cup ?\cup G_p$ is the disjoint union of graphs $G_1,G_2,\dots ,G_p$ and $f=f_1\cup f_2\cup ?\cup f_p$, then $m_c(G,f)={\prod }_{i=1}^p{m}_c(G_i,f_i)$ and $m_p(G,f)={\prod }_{i=1}^p{m}_p(G_i,f_i)$. This generalizes a result in Carraher et al. (2014), where the case each $G_i$ is a copy of $K_1$ is considered.     

Matchings,path covers and domination

We show that if $G$ is a graph with minimum degree at least three, then ${\gamma }_t\left(G\right)\le {\alpha }^{\prime }\left(G\right)+(\mathrm{pc}\left(G\right)?1)∕2$ and this bound is tight, where ${\gamma }_t\left(G\right)$ is the total domination number of $G$, ${\alpha }^{\prime }\left(G\right)$ the matching number of $G$ and $\mathrm{pc}\left(G\right)$ the path covering number of $G$ which is the minimum number of vertex disjoint paths such that every vertex belongs to a path in the cover. We show that if $G$ is a connected graph on at least six vertices, then ${\gamma }_{\mathrm{nt}}\left(G\right)\le {\alpha }^{\prime }\left(G\right)+\mathrm{pc}\left(G\right)∕2$ and this bound is tight, where ${\gamma }_{\mathrm{nt}}\left(G\right)$ denotes the neighborhood total domination number of $G$. We observe that every graph $G$ of order $n$ satisfies ${\alpha }^{\prime }\left(G\right)+\mathrm{pc}\left(G\right)∕2\ge n∕2$, and we characterize the trees achieving equality in this bound.