The list L(2,1)-labeling of planar graphs

Let $\mathbf{N}$ be the set of all positive integers. A list assignment of a graph $G$ is a function $L:V\left(G\right)?2^{\mathbf{N}}$ that assigns each vertex $v$ a list $L\left(v\right)$ for all $v\in V\left(G\right)$. We say that $G$ is $L$-$(2,1)$-choosable if there exists a function $?$ such that $?\left(v\right)\in L\left(v\right)$ for all $v\in V\left(G\right)$, $|?\left(u\right)??\left(v\right)|\ge 2$ if $u$ and $v$ are adjacent, and $|?\left(u\right)??\left(v\right)|\ge 1$ if $u$ and $v$ are at distance 2. The list-$L(2,1)$-labeling number ${\lambda }_l\left(G\right)$ of $G$ is the minimum $k$ such that for every list assignment $L=\{L\left(v\right):|L\left(v\right)|=k,v\in V\left(G\right)\}$, $G$ is $L$-$(2,1)$-choosable. We prove that if $G$ is a planar graph with girth $g\ge 8$ and its maximum degree $\Delta$ is large enough, then ${\lambda }_l\left(G\right)\le \Delta +3$. There are graphs with large enough $\Delta$ and $g\ge 8$ having ${\lambda }_l\left(G\right)=\Delta +3$.     

Degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number

Let $D$ be a finite and simple digraph with vertex set $V\left(D\right)$. For a vertex $v\in V\left(D\right)$, the degree $d\left(v\right)$ of $v$ is defined as the minimum value of its out-degree $d^{+}\left(v\right)$ and its in-degree $d^{?}\left(v\right)$. If $D$ is a graph or a digraph with minimum degree $\delta$ and edge-connectivity $\lambda$, then $\lambda \le \delta$. A graph or a digraph is maximally edge-connected if $\lambda =\delta$. A graph or a digraph is called super-edge-connected if every minimum edge-cut consists of edges adjacent to or from a vertex of minimum degree.In this note we present degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number of the underlying graph.     

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

Homomorphism complexes and k-cores

For any fixed graph $G$, we prove that the topological connectivity of the graph homomorphism complex Hom($G,K_m$) is at least $m?D\left(G\right)?2$, where $D\left(G\right)={max}_{H?G}\delta \left(H\right)$, for $\delta \left(H\right)$ the minimum degree of a vertex in a subgraph $H$. This generalizes a theorem of C?uki? and Kozlov, in which the maximum degree $\Delta \left(G\right)$ was used in place of $D\left(G\right)$, and provides a high-dimensional analogue of the graph theoretic bound for chromatic number, $\chi \left(G\right)\le D\left(G\right)+1$, as $\chi \left(G\right)=min\{m:\text{Hom}(G,K_m)\ne ?\}$. Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes Hom$(G(n,p),K_m)$ when $p=c∕n$ for a fixed constant $c>0$.     

Counting arithmetical structures on paths and cycles

Let $G$ be a finite, connected graph. An arithmetical structure on $G$ is a pair of positive integer vectors $\mathbf{d},\mathbf{r}$ such that $(diag\left(\mathbf{d}\right)?A)\mathbf{r}=0$, where $A$ is the adjacency matrix of $G$. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the torsion part of the cokernels of the matrices $(diag\left(\mathbf{d}\right)?A)$). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients $\left(\genfrac{}{}{0ex}{}{2n?1}{n?1}\right)$, and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.     

Toll number of the Cartesian and the lexicographic product of graphs

Toll convexity is a variation of the so-called interval convexity. A tolled walk $T$ between two non-adjacent vertices $u$ and $v$ in a graph $G$ is a walk, in which $u$ is adjacent only to the second vertex of $T$ and $v$ is adjacent only to the second-to-last vertex of $T$. A toll interval between $u,v\in V\left(G\right)$ is a set $T_G(u,v)=\{x\in V\left(G\right):x\text{ lies on a tolled walk between }u\text{ and }v\}$. A set $S?V\left(G\right)$ is toll convex, if $T_G(u,v)?S$ for all $u,v\in S$. A toll closure of a set $S?V\left(G\right)$ is the union of toll intervals between all pairs of vertices from $S$. The size of a smallest set $S$ whose toll closure is the whole vertex set is called a toll number of a graph $G$, $tn\left(G\right)$. The first part of the paper reinvestigates the characterization of convex sets in the Cartesian product of two graphs. It is proved that the toll number of the Cartesian product of two graphs equals 2. In the second part, the toll number of the lexicographic product of two graphs is studied. It is shown that if $H$ is not isomorphic to a complete graph, $tn(G°H)\le 3?tn\left(G\right)$. We give some necessary and sufficient conditions for $tn(G°H)=3?tn\left(G\right)$. Moreover, if $G$ has at least two extreme vertices, a complete characterization is given. Furthermore, graphs with $tn(G°H)=2$ are characterized. Finally, the formula for $tn(G°H)$ is given — it is described in terms of the so-called toll-dominating triples or, if $H$ is complete, toll-dominating pairs.     

Total list weighting of graphs with bounded maximum average degree

A proper total weighting of a graph $G$ is a mapping $?$ which assigns to each vertex and each edge of $G$ a real number as its weight so that for any edge $uv$ of $G$, ${\sum }_{e\in E\left(v\right)}?\left(e\right)+?\left(v\right)\ne {\sum }_{e\in E\left(u\right)}?\left(e\right)+?\left(u\right)$. A $(k,k^{\prime })$-list assignment of $G$ is a mapping $L$ which assigns to each vertex $v$ a set $L\left(v\right)$ of $k$ permissible weights and to each edge $e$ a set $L\left(e\right)$ of $k^{\prime }$ permissible weights. An $L$-total weighting is a total weighting $?$ with $?\left(z\right)\in L\left(z\right)$ for each $z\in V\left(G\right)\cup E\left(G\right)$. A graph $G$ is called $(k,k^{\prime })$-choosable if for every $(k,k^{\prime })$-list assignment $L$ of $G$, there exists a proper $L$-total weighting. It was proved in Tang and Zhu (2017) that if $p\in \{5,7,11\}$, a graph $G$ without isolated edges and with $\mathrm{mad}\left(G\right)\le p?1$ is $(1,p)$-choosable. In this paper, we strengthen this result by showing that for any prime $p$, a graph $G$ without isolated edges and with $\mathrm{mad}\left(G\right)\le p?1$ is $(1,p)$-choosable.     

Improving the Clark–Suen bound on the domination number of the Cartesian product of graphs

A long-standing Vizing’s conjecture asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers; one of the most significant results related to the conjecture is the bound of Clark and Suen, $\gamma (G\square H)\ge \gamma \left(G\right)\gamma \left(H\right)∕2$, where $\gamma$ stands for the domination number, and $G\square H$ is the Cartesian product of graphs $G$ and $H$. In this note, we improve this bound by employing the 2-packing number $\rho \left(G\right)$ of a graph $G$ into the formula, asserting that $\gamma (G\square H)\ge (2\gamma \left(G\right)?\rho \left(G\right))\gamma \left(H\right)∕3$. The resulting bound is better than that of Clark and Suen whenever $G$ is a graph with $\rho \left(G\right)<\gamma \left(G\right)∕2$, and in the case $G$ has diameter 2 reads as $\gamma (G\square H)\ge (2\gamma \left(G\right)?1)\gamma \left(H\right)∕3$.     

Unimodality of independence polynomials of the incidence product of graphs

Given two graphs $G$ and $H$, assume that $V\left(G\right)=\{v_1,v_2,\dots ,v_n\}$ and $U$ is a subset of $V\left(H\right)$. We introduce a new graph operation called the incidence product, denoted by $G\odot H^U$, as follows: insert a new vertex into each edge of $G$, then join with edges those pairs of new vertices on adjacent edges of $G$. Finally, for every vertex $v_i\in V\left(G\right)$, replace it by a copy of the graph $H$ and join every new vertex being adjacent to $v_i$ to every vertex of $U$. It generalizes the line graph operation. We prove that the independence polynomial

$I\left(G\odot H^U;x\right)=I^n(H;x)M\left(G;\frac{x{I}^2(H?U;x)}{I^2(H;x)}\right),$

where $M(G;x)$ is its matching polynomial. Based on this formula, we show that the incidence product of some graphs preserves symmetry, unimodality, reality of zeros of independence polynomials. As applications, we obtain some graphs so-formed having symmetric and unimodal independence polynomials. In particular, the graph $Q\left(G\right)$ introduced by Cvetkovi?, Doob and Sachs has a symmetric and unimodal independence polynomial.     

On 3-stable number conditions in n-connected claw-free graphs

For a subgraph $X$ of $G$, let ${\alpha }_G^3\left(X\right)$ be the maximum number of vertices of $X$ that are pairwise distance at least three in $G$. In this paper, we prove three theorems. Let $n$ be a positive integer, and let $H$ be a subgraph of an $n$-connected claw-free graph $G$. We prove that if $n\ge 2$, then either $H$ can be covered by a cycle in $G$, or there exists a cycle $C$ in $G$ such that ${\alpha }_G^3(H?V\left(C\right))\le {\alpha }_G^3\left(H\right)?n$. This result generalizes the result of Broersma and Lu that $G$ has a cycle covering all the vertices of $H$ if ${\alpha }_G^3\left(H\right)\le n$. We also prove that if $n\ge 1$, then either $H$ can be covered by a path in $G$, or there exists a path $P$ in $G$ such that ${\alpha }_G^3(H?V\left(P\right))\le {\alpha }_G^3\left(H\right)?n?1$. By using the second result, we prove the third result. For a tree $T$, a vertex of $T$ with degree one is called a leaf of $T$. For an integer $k\ge 2$, a tree which has at most $k$ leaves is called a $k$-ended tree. We prove that if ${\alpha }_G^3\left(H\right)\le n+k?1$, then $G$ has a $k$-ended tree covering all the vertices of $H$. This result gives a positive answer to the conjecture proposed by Kano et al. (2012).