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$.     

A note on the list vertex arboricity of toroidal graphs

The vertex arboricity $a\left(G\right)$ of a graph $G$ is the minimum number of colors required to color the vertices of $G$ such that no cycle is monochromatic. The list vertex arboricity $a_l\left(G\right)$ is the list-coloring version of this concept. In this note, we prove that if $G$ is a toroidal graph, then $a_l\left(G\right)\le 4$; and $a_l\left(G\right)=4$ if and only if $G$ contains $K_7$ as an induced subgraph.     

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)$.     

Global defensive alliances of trees and Cartesian product of paths and cycles

Given a graph $G$, a defensive alliance of $G$ is a set of vertices $S?V\left(G\right)$ satisfying the condition that for each $v\in S$, at least half of the vertices in the closed neighborhood of $v$ are in $S$. A defensive alliance $S$ is called global if every vertex in $V\left(G\right)?S$ is adjacent to at least one member of the defensive alliance $S$. The global defensive alliance number of $G$, denoted ${\gamma }_a\left(G\right)$, is the minimum size around all the global defensive alliances of $G$. In this paper, we present an efficient algorithm to determine the global defensive alliance numbers of trees, and further give formulas to decide the global defensive alliance numbers of complete $k$-ary trees for $k=2,3,4$. We also establish upper bounds and lower bounds for ${\gamma }_a(P_m\times P_n),{\gamma }_a(C_m\times P_n)$ and ${\gamma }_a(C_m\times C_n)$, and show that the bounds are sharp for certain $m,n$.     

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.     

Sum choice number of generalized θ-graphs

Let $G=\left(VE\right)$ be a simple graph and for every vertex $v\in V$ let $L\left(v\right)$ be a set (list) of available colors. $G$ is called $L$-colorable if there is a proper coloring $\phi$ of the vertices with $\phi \left(v\right)\in L\left(v\right)$ for all $v\in V$. A function $f:V\to \mathbb{N}$ is called a choice function of $G$ and $G$ is said to be $f$-list colorable if $G$ is $L$-colorable for every list assignment $L$ choice function is defined by $size\left(f\right)={\sum }_{v\in V}f\left(v\right)$ and the sum choice number ${\chi }_{sc}\left(G\right)$ denotes the minimum size of a choice function of $G$.Sum list colorings were introduced by Isaak in 2002 and got a lot of attention since then.For $r\ge 3$ a generalized ${\theta }_{k_1{k}_2\dots k_r}$-graph is a simple graph consisting of two vertices $v_1$ and $v_2$ connected by $r$ internally vertex disjoint paths of lengths $k_1,k_2,\dots ,k_r$ $(k_1\le k_2\le ?\le k_r)$.In 2014, Carraher et al. determined the sum-paintability of all generalized $\theta$-graphs which is an online-version of the sum choice number and consequently an upper bound for it.In this paper we obtain sharp upper bounds for the sum choice number of all generalized $\theta$-graphs with $k_1\ge 2$ and characterize all generalized $\theta$-graphs $G$ which attain the trivial upper bound $\left|V\left(G\right)\right|+\left|E\left(G\right)\right|$.     

The expansion of a chord diagram and the Tutte polynomial

A chord diagram is a set of chords of a circle such that no pair of chords has a common endvertex. A chord diagram $E$ is called nonintersecting if $E$ contains no crossing. For a chord diagram $E$ having a crossing $S=\{x_1{x}_3,x_2{x}_4\}$, the expansion of $E$ with respect to $S$ is to replace $E$ with $E_1=(E?S)\cup \{x_2{x}_3,x_4{x}_1\}$ or $E_2=(E?S)\cup \{x_1{x}_2,x_3{x}_4\}$. For a chord diagram $E$, let $f\left(E\right)$ be the chord expansion number of $E$, which is defined as the cardinality of the multiset of all nonintersecting chord diagrams generated from $E$ with a finite sequence of expansions.In this paper, it is shown that the chord expansion number $f\left(E\right)$ equals the value of the Tutte polynomial at the point $(2,?1)$ for the interlace graph $G_E$ corresponding to $E$. The chord expansion number of a complete multipartite chord diagram is also studied. An extended abstract of the paper was published (Nakamigawa and Sakuma, 2017) [13].     

A sharp lower bound on Steiner Wiener index for trees with given diameter

Let $G$ be a connected graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. For a subset $S$ of $V\left(G\right)$, the Steiner distance$d\left(S\right)$ of $S$ is the minimum size of a connected subgraph whose vertex set contains $S$. For an integer $k$ with $2\le k\le n?1$, the Steiner$k$-Wiener index${\text{SW}}_k\left(G\right)$ is ${\sum }_{S?V\left(G\right),\left|S\right|=k}d\left(S\right)$. In this paper, we introduce some transformations for trees that do not increase their Steiner $k$-Wiener index for $2\le k\le n?1$. Using these transformations, we get a sharp lower bound on Steiner $k$-Wiener index for trees with given diameter, and obtain the corresponding extremal graph as well.     

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$.