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.     

On mutually independent hamiltonian paths

Let $P_1=〈v_1,v_2,v_3,\dots ,v_n〉$ and $P_2=〈u_1,u_2,u_3,\dots ,u_n〉$ be two hamiltonian paths of $G$. We say that $P_1$ and $P_2$ are independent if $u_1=v_1,u_n=v_n$, and $u_i\ne v_i$ for $1<i<n$. We say a set of hamiltonian paths $P_1,P_2,\dots ,P_s$ of $G$ between two distinct vertices are mutually independent if any two distinct paths in the set are independent. We use $n$ to denote the number of vertices and use $e$ to denote the number of edges in graph $G$. Moreover, we use $\bar{e}$ to denote the number of edges in the complement of $G$. Suppose that $G$ is a graph with $\bar{e}\le n-4$ and $n\ge 4$. We prove that there are at least $n-2-\bar{e}$ mutually independent hamiltonian paths between any pair of distinct vertices of $G$ except $n=5$ and $\bar{e}=1$. Assume that $G$ is a graph with the degree sum of any two non-adjacent vertices being at least $n+2$. Let $u$ and $v$ be any two distinct vertices of $G$. We prove that there are ${deg}_G\left(u\right)+{deg}_G\left(v\right)-n$ mutually independent hamiltonian paths between $u$ and $v$ if $(u,v)\in E\left(G\right)$ and there are ${deg}_G\left(u\right)+{deg}_G\left(v\right)-n+2$ mutually independent hamiltonian paths between $u$ and $v$ if otherwise.     

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

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

Maximum average degree and relaxed coloring

We say a graph is $(d,d,\dots ,d,0,\dots ,0)$-colorable with $a$ of $d$’s and $b$ of $0$’s if $V\left(G\right)$ may be partitioned into $b$ independent sets $O_1,O_2,\dots ,O_b$ and $a$ sets $D_1,D_2,\dots ,D_a$ whose induced graphs have maximum degree at most $d$. The maximum average degree, $mad\left(G\right)$, of a graph $G$ is the maximum average degree over all subgraphs of $G$. In this note, for nonnegative integers $a,b$, we show that if $mad\left(G\right)<\frac{4}{3}a+b$, then $G$ is $(1_1,1_2,\dots ,1_a,0_1,\dots ,0_b)$-colorable.     

Some multicolor bipartite Ramsey numbers involving cycles and a small number of colors

For bipartite graphs $G_1,G_2,\dots ,G_k$, the bipartite Ramsey number $b(G_1,G_2,\dots ,G_k)$ is the least positive integer $b$ so that any coloring of the edges of $K_{b,b}$ with $k$ colors will result in a copy of $G_i$ in the $i$th color for some $i$. In this paper, our main focus will be to bound the following numbers: $b(C_{2t_1},C_{2t_2})$ and $b(C_{2t_1},C_{2t_2},C_{2t_3})$ for all $t_i\ge 3,$$b(C_{2t_1},C_{2t_2},C_{2t_3},C_{2t_4})$ for $3\le t_i\le 9,$ and $b(C_{2t_1},C_{2t_2},C_{2t_3},C_{2t_4},C_{2t_5})$ for $3\le t_i\le 5.$ Furthermore, we will also show that these mentioned bounds are generally better than the bounds obtained by using the best known Zarankiewicz-type result.     

Extremal product-one free sequences in Dihedral and Dicyclic Groups

Let $G$ be a finite group, written multiplicatively. The Davenport constant of $G$ is the smallest positive integer $D\left(G\right)$ such that every sequence of $G$ with $D\left(G\right)$ elements has a non-empty subsequence with product $1$. Let $D_{2n}$ be the Dihedral Group of order $2n$ and $Q_{4n}$ be the Dicyclic Group of order $4n$. Zhuang and Gao (2005) showed that $D\left(D_{2n}\right)=n+1$ and Bass (2007) showed that $D\left(Q_{4n}\right)=2n+1$. In this paper, we give explicit characterizations of all sequences $S$ of $G$ such that $\left|S\right|=D\left(G\right)?1$ and $S$ is free of subsequences whose product is 1, where $G$ is equal to $D_{2n}$ or $Q_{4n}$ for some $n$.