A note on planar graphs with large width parameters and small grid-minors

Given a graph $G$ with tree-width $\omega \left(G\right)$, branch-width $\beta \left(G\right)$, and side size of the largest square grid-minor $\theta \left(G\right)$, it is known that $\theta \left(G\right)\le \beta \left(G\right)\le \omega \left(G\right)+1\le \frac{3}{2}\beta \left(G\right)$. In this paper, we introduce another approach to bound the side size of the largest square grid-minor specifically for planar graphs. The approach is based on measuring the distances between the faces in an embedding of a planar graph. We analyze the tightness of all derived bounds. In particular, we present a class of planar graphs where $\theta \left(G\right)=\beta \left(G\right)<\omega \left(G\right)=?\frac{3}{2}\theta \left(G\right)??1$.     

The NLC-width and clique-width for powers of graphs of bounded tree-width

The $k$-power graph of a graph $G$ is a graph with the same vertex set as $G$, in that two vertices are adjacent if and only if, there is a path between them in $G$ of length at most $k$. A $k$-tree-power graph is the $k$-power graph of a tree, a $k$-leaf-power graph is the subgraph of some $k$-tree-power graph induced by the leaves of the tree.We show that (1) every $k$-tree-power graph has NLC-width at most $k+2$ and clique-width at most $k+2+max\{?\frac{k}{2}??1,0\}$, (2) every $k$-leaf-power graph has NLC-width at most $k$ and clique-width at most $k+max\{?\frac{k}{2}??2,0\}$, and (3) every $k$-power graph of a graph of tree-width $l$ has NLC-width at most ${(k+1)}^{l+1}?1$, and clique-width at most $2?{(k+1)}^{l+1}?2$.     

Strong vertex-magic and edge-magic labelings of 2-regular graphs of odd order using Kotzig completion

Let $G$ be a 2-regular graph with $2m+1$ vertices and assume that $G$ has a strong vertex-magic total labeling. It is shown that the four graphs $G\cup 2m{C}_3$, $G\cup (2m+2)C_3$, $G\cup m{C}_8$ and $G\cup (m+1)C_8$ also have a strong vertex-magic total labeling. These theorems follow from a new use of carefully prescribed Kotzig arrays. To illustrate the power of this technique, we show how just three of these arrays, combined with known labelings for smaller 2-regular graphs, immediately provide strong vertex-magic total labelings for 68 different 2-regular graphs of order 49.     

Essential edge connectivity of line graphs

Let $G$ be a graph and $L\left(G\right)$ be its line graph. In 1969, Chartrand and Stewart proved that ${\kappa }^{\prime }\left(L\left(G\right)\right)\ge 2{\kappa }^{\prime }\left(G\right)?2$, where ${\kappa }^{\prime }\left(G\right)$ and ${\kappa }^{\prime }\left(L\left(G\right)\right)$ denote the edge connectivity of $G$ and $L\left(G\right)$ respectively. We show a similar relationship holds for the essential edge connectivity of $G$ and $L\left(G\right)$, written ${\kappa }_e^{\prime }\left(G\right)$ and ${\kappa }_e^{\prime }\left(L\left(G\right)\right)$, respectively. In this note, it is proved that if $L\left(G\right)$ is not a complete graph and $G$ does not have a vertex of degree two, then ${\kappa }_e^{\prime }\left(L\left(G\right)\right)\ge 2{\kappa }_e^{\prime }\left(G\right)?2$. An immediate corollary is that $\kappa \left(L^2\left(G\right)\right)\ge 2\kappa \left(L\left(G\right)\right)?2$ for such graphs $G$, where the vertex connectivity of the line graph $L\left(G\right)$ and the second iterated line graph $L^2\left(G\right)$ are written as $\kappa \left(L\left(G\right)\right)$ and $\kappa \left(L^2\left(G\right)\right)$ respectively.     

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

Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs

An interval$t$-coloring of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors of the edges incident with every vertex of $G$ are colored by consecutive colors. A cyclic interval$t$-coloring of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors of the edges incident with every vertex of $G$ are colored by consecutive colors, under the condition that color $1$ is considered as consecutive to color $t$. Denote by $w\left(G\right)$ ($w_c\left(G\right)$) and $W\left(G\right)$ ($W_c\left(G\right)$) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph $G$, respectively. We present some new sharp bounds on $w\left(G\right)$ and $W\left(G\right)$ for multigraphs $G$ satisfying various conditions. In particular, we show that if $G$ is a $2$-connected multigraph with an interval coloring, then $W\left(G\right)\le 1+?\frac{\left|V\left(G\right)\right|}{2}?(\Delta \left(G\right)?1)$. We also give several results towards the general conjecture that $W_c\left(G\right)\le \left|V\left(G\right)\right|$ for any triangle-free graph $G$ with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most $4$.     

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

List star chromatic index of sparse graphs

A star edge-coloring of a graph $G$ is a proper edge coloring such that every 2-colored connected subgraph of $G$ is a path of length at most 3. For a graph $G$, let the list star chromatic index of $G$, $c{h}_s^{\prime }\left(G\right)$, be the minimum $k$ such that for any $k$-uniform list assignment $L$ for the set of edges, $G$ has a star edge-coloring from $L$. Dvo?ák et al. (2013) asked whether the list star chromatic index of every subcubic graph is at most 7. In Kerdjoudj et al. (2017) we proved that it is at most 8. In this paper we consider graphs with any maximum degree, we proved that if the maximum average degree of a graph $G$ is less than $\frac{14}{5}$ (resp. 3), then $c{h}_s^{\prime }\left(G\right)\le 2\Delta \left(G\right)+2$ (resp. $c{h}_s^{\prime }\left(G\right)\le 2\Delta \left(G\right)+3$).     

On disjoint matchings in cubic graphs

For $i=2,3$ and a cubic graph $G$ let ${\nu }_i\left(G\right)$ denote the maximum number of edges that can be covered by $i$ matchings. We show that ${\nu }_2\left(G\right)\ge \frac{4}{5}\left|V\left(G\right)\right|$ and ${\nu }_3\left(G\right)\ge \frac{7}{6}\left|V\left(G\right)\right|$. Moreover, it turns out that ${\nu }_2\left(G\right)\le \frac{\left|V\left(G\right)\right|+2{\nu }_3\left(G\right)}{4}$.