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

Ramsey numbers of odd cycles versus larger even wheels

The generalized Ramsey number $R(G_1,G_2)$ is the smallest positive integer $N$ such that any red–blue coloring of the edges of the complete graph $K_N$ either contains a red copy of $G_1$ or a blue copy of $G_2$. Let $C_m$ denote a cycle of length $m$ and $W_n$ denote a wheel with $n+1$ vertices. In 2014, Zhang, Zhang and Chen determined many of the Ramsey numbers $R(C_{2k+1},W_n)$ of odd cycles versus larger wheels, leaving open the particular case where $n=2j$ is even and $k<j<3k∕2$. They conjectured that for these values of $j$ and $k$, $R(C_{2k+1},W_{2j})=4j+1$. In 2015, Sanhueza-Matamala confirmed this conjecture asymptotically, showing that $R(C_{2k+1},W_{2j})\le 4j+334$. In this paper, we prove the conjecture of Zhang, Zhang and Chen for almost all of the remaining cases. In particular, we prove that $R(C_{2k+1},W_{2j})=4j+1$ if $j?k\ge 251$, $k<j<3k∕2$, and $j\ge 212299$.     

Moplex orderings generated by the LexDFS algorithm

Let $G$ be a graph with vertex set $V$. A moplex of $G$ is both a clique and a module whose neighborhood is a minimal separator in $G$ or empty. A moplex ordering of $G$ is an ordered partition $(X_1,X_2,?,X_k)$ of $V$ for some integer $k$ into moplexes which are defined in the successive transitory elimination graphs, i.e., for $1?i?k?1$, $X_i$ is a moplex of the graph $G_i$ induced by ${\cup }_{j=i}^k{X}_j$ and $X_k$ induces a clique. In this paper we prove the terminal vertex by an execution of the lexicographical depth-first search (LexDFS for short) algorithm on $G$ belongs to a moplex whose vertices are numbered consecutively and further that the LexDFS algorithm on $G$ defines a moplex ordering of $G$, which is similar to the result about the maximum cardinality search (MCS for short) algorithm on chordal graphs [J.R.S. Blair, B.W. Peyton, An introduction to chordal graphs and clique trees, IMA Volumes in Mathematics and its Applications, 56 (1993) pp. 1–30] and the result about the lexicographical breadth-first search (LexBFS for short) algorithm on general graphs [A. Berry, J.-P. Bordat, Separability generalizes Dirac’s theorem, Discrete Appl. Math., 84 (1998) 43–53]. As a corollary, we can obtain a simple algorithm on a chordal graph to generate all minimal separators and all maximal cliques.     

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

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

Fixed-parameter algorithms for vertex cover P3

Let $P_{\ell }$ denote a path in a graph $G=(V,E)$ with $\ell$ vertices. A vertex cover $P_{\ell }$ set $C$ in $G$ is a vertex subset such that every $P_{\ell }$ in $G$ has at least a vertex in $C$. The Vertex Cover$P_{\ell }$ problem is to find a vertex cover $P_{\ell }$ set of minimum cardinality in a given graph. This problem is NP-hard for any integer $\ell ⩾2$. The parameterized version of Vertex Cover$P_{\ell }$ problem called $k$-Vertex Cover$P_{\ell }$ asks whether there exists a vertex cover $P_{\ell }$ set of size at most $k$ in the input graph. In this paper, we give two fixed parameter algorithms to solve the $k$-Vertex Cover$P_3$ problem. The first algorithm runs in time $O^1\left(1.7964^k\right)$ in polynomial space and the second algorithm runs in time $O^1\left(1.7485^k\right)$ in exponential space. Both algorithms are faster than previous known fixed-parameter algorithms.     

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.     

Proper connection and size of graphs

An edge-coloured graph $G$ is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a connected graph $G,$ denoted by $\mathrm{pc}\left(G\right)$, is the smallest number of colours that are needed in order to make $G$ properly connected. Our main result is the following: Let $G$ be a connected graph of order $n$ and $k\ge 2$. If $\left|E\left(G\right)\right|\ge \left(\genfrac{}{}{0ex}{}{n?k?1}{2}\right)+k+2$, then $\mathrm{pc}\left(G\right)\le k$ except when $k=2$ and $G\in \{G_1,G_2\},$ where $G_1=K_1\vee (2K_1+K_2)$ and $G_2=K_1\vee (K_1+2K_2).$     

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.     

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.     

On (Kq,k) vertex stable graphs with minimum size

A graph $G$ is a $(K_q,k)$ vertex stable graph if it contains a $K_q$ after deleting any subset of $k$ vertices. We give a characterization of $(K_q,k)$ vertex stable graphs with minimum size for $q=3,4,5$.