For a connected graph $G$ of order $3$ or more and an edge coloring $c:E(G)\to {\mathbb{Z}}_k$ ($k\ge 2$) where adjacent edges may be colored the same, the color sum $s(v)$ of a vertex $v$ of $G$ is the sum in ${\mathbb{Z}}_k$ of the colors of the edges incident with $v$. The edge coloring $c$ is a modular $k$-edge coloring of $G$ if $s(u)\ne s(v)$ in ${\mathbb{Z}}_k$ for all pairs $u,v$ of adjacent vertices in $G$. The modular chromatic index ${\chi }_m^{\prime }(G)$ of $G$ is the minimum $k$ for which $G$ has a modular $k$-edge coloring. It is shown that $\chi (G)\le {\chi }_m^{\prime }(G)\le \chi (G)+1$ for every connected graph $G$ of order at least 3, where $\chi (G)$ is the chromatic number of $G$. Furthermore, it is shown that ${\chi }_m^{\prime }(G)=\chi (G)+1$ if and only if $\chi (G)\equiv 2(\mathrm{mod}4)$ and every proper $\chi (G)$-coloring of $G$ results in color classes of odd size.

It is known that an $\alpha$-labeling of a bipartite graph $G$ with $n$ edges can be used to obtain a cyclic $G$-decomposition of $K_{2nx+1}$ for every positive integer $x$. It is also known that if two graphs $G$ and $H$ admit a free $a$-labeling, then their vertex-disjoint union also admits a free $\alpha$-labeling. We show that if $G$ is a bipartite prism, a bipartite Möbius ladder, or a connected cubic bipartite graph of order at most 14, then $G$ admits a free $a$-labeling. We conjecture that every bipartite cubic graph admits a free $\alpha$-labeling.

Here we present a characterization of Sheffer-type polynomial sequences based on the isomorphism between the Riordan group and Sheffer group and the sequence characterization of Riordan arrays. We also give several alternative forms of the characterization of the Riordan group, Sheffer group, and their subgroups. Formulas for the computation of the generating functions of Riordan arrays and Sheffer-type polynomial sequences from the characteristics are shown. Furthermore, the applications of the characteristics to lattice walks and recursive construction of Sheffer-type polynomial sequences are also given.

A set of $S$ edge-disjoint Hamilton cycles in a graph $G$ is said to be $maximal$ if the Hamilton cycles in $S$ form a subgraph of $G$ such that $G–E(S)$ has no Hamilton cycle. The set of integers $m$ for which a graph $G$ contains a maximal set of $m$ edge-disjoint Hamilton cycles has previously been determined whenever $G$ is a complete graph, a complete bipartite graph, and in many cases when $G$ is a complete multipartite graph. In this paper, we solve half of the remaining open cases regarding complete multipartite graphs.

For an outerplanar graph on $n$ vertices, we determine the maximum number of vertices of degree at least $k$. For $k=4$ (and $n\ge 7$) the answer is $n–4$. For $k=5$ (and $n\ge 4$), the answer is $\lfloor \frac{2(n-4)}{3}\rfloor$ (except one less when $n\equiv 1(\mathrm{mod}6)$). For $k\ge 6$ (and $n\ge k+2$), the answer is $\lfloor \frac{n-6}{k-4}\rfloor$. We also determine the maximum sum of the degrees of $s$ vertices in an $n$-vertex outerplanar graph and the maximum sum of the degrees of the vertices with degree at least $k$.

For a connected graph $G$ and a positive integer $k$, the $k$th power $G^k$ of $G$ is the graph with $V(G^k)=V(G)$ where $uv\in E(G^k)$ if the distance $d_G(u,v)$ between $u$ and $v$ is at most $k$. The edge coloring of $G^k$ defined by assigning each edge $uv$ of $G^k$ the color $d_G(u,v)$ produces an edge-colored graph $G^k$ called a distance-colored graph. A distance-colored graph is properly $p$-connected if every two distinct vertices $u$ and $v$ in the graph are connected by $p$ internally disjoint properly colored $u$-$v$ paths. It is shown that $G^2$ is properly $2$-connected for every $2$-connected graph that is not complete, a double star is the only tree $T$ for which $T^2$ is properly $2$-connected, and $G^3$ is properly $2$-connected for every connected graph $G$ of diameter at least $3$. All pairs $k,n$ of positive integers for which $P_n^k$ is properly $k$-connected are determined. It is shown that every properly colored graph $H$ with ${\chi }^{\prime }(H)$ colors is a subgraph of some distance-colored graph and the question of determining the smallest order of such a graph is studied.

Let $G$ be a simple graph with vertex set $V(G)$ and edge set $E(G)$, and let ${\mathbb{Z}}_2=\{0,1\}$. Any edge labeling $f$ induces a partial vertex labeling $f^{+}:V(G)\to {\mathbb{Z}}_2$ assigning $0$ or $1$ to $f^{+}(v)$, $v$ being an element of $V(G)$, depending on whether there are more $0$-edges or $1$-edges incident with $v$, and no label is given to $f^{+}(v)$ otherwise. For each $i\in {\mathbb{Z}}_2$, let $v_f(i)=|\{v\in V(G):f^{+}(v)=i\}|$ and let $e_f(i)=|\{e\in E(G):f(e)=i\}|$. An edge-labeling $f$ of $G$ is said to be edge-friendly if $|e_f(0)–e_f(1)|\le 1$. The edge-balance index set of the graph $G$ is defined as $EBI(G)=\{|v_f(0)–v_f(1)|:f\text{ is edge-friendly}\}$. In this paper, exact values of the edge-balance index sets of $L$-product of cycles with stars, $C_n{\times }_L(S_t(m),c)$, where $m$ is even, and $c$ is the center of the star graph are presented.

We investigate group divisible designs with two association classes (known as GDDS, GADs or PBIBDs) with block size 3 and unequal size groups. We completely determine the necessary and sufficient conditions for groups with size vector $(n,1)$ for any $n\ge 3$, and $(n,2,1)$ for $n\in \{2,3,\dots ,6\}$. We also have some general results for $(n_1,n_2,n_3)$.

A mutation of a vertex-magic total labeling of a graph $G$ is a swap of some set of edges incident on one vertex of $G$ with some set of edges incident with another vertex where the labels on the two sets have the same sum. Mutation has previously been seen to be a useful method for producing new labelings from old. In this paper, we study mutations which mutate labelings of regular graphs into labelings of other regular graphs. We present results of extensive computations which confirm how prolific this procedure is. These computations add weight to MacDougall’s conjecture that all non-trivial regular graphs are vertex-magic.

A Langford-type $m$-tuple difference set of order $t$ and defect $d$ is a set of $t$ $m$-tuples $\{(d_{i,1},d_{i,2},\dots ,d_{i,m})\mid i=1,2,\dots ,t\}$ such that $d_{i,1}+d_{i,2}+\cdots +d_{i,m}=0$ for $1\le i\le t$ and $\{|d_{i,j}|\mid 1\le i\le t,1\le j\le m\}=\{d,d+1,\dots ,d+mt-1\}$. In this paper, we give necessary and sufficient conditions on $t$ and $d$ for the existence of a Langford-type $m$-tuple difference set of order $t$ and defect $d$ when $m\equiv 0,2(\mathrm{mod}4)$. In the case that $m\equiv 1,3(\mathrm{mod}4)$, we provide sufficient conditions for the existence of a Langford-type $m$-tuple difference set of order $t$ and defect $d$ when $d$ is at most about $t/2$. Using these results, we obtain cyclic $m$-cycle systems of the circulant graph $⟨d,d+1,\dots ,d+mt-1{⟩}_n$ for all $n\ge 2(d+mt)-1$ with $d$ and $t$ satisfying certain conditions.

We give a computer-assisted proof of the fact that $R(K_5–P_3,K_5)=25$. This solves one of the three remaining open cases in Hendry’s table, which listed the Ramsey numbers for pairs of graphs on 5 vertices. We find that there exist no $(K_5–P_3,K_5)$-good graphs containing a $K_4$ on 23 or 24 vertices, where a graph $F$ is $(G,H)$-good if $F$ does not contain $G$ and the complement of $F$ does not contain $H$. The unique $(K_5–P_3,K_5)$-good graph containing a $K_4$ on 22 vertices is presented.

A group divisible design (GDD) $(v=v_1+v_2+\cdots +v_g,g,k;{\lambda }_1,{\lambda }_2)$ is an ordered pair $(V,\mathcal{B})$ where $V$ is a $v$-set of symbols and $\mathcal{B}$ is a collection of $k$-subsets (called blocks) of $V$ satisfying the following properties: the $v$-set is divided into $g$ groups of sizes $v_1,v_2,\dots ,v_g$; each pair of symbols from the same group occurs in exactly ${\lambda }_1$ blocks in $\mathcal{B}$; and each pair of symbols from different groups occurs in exactly ${\lambda }_2$ blocks in $\mathcal{B}$. In this paper we give necessary conditions on $m$ and $n$ for the existence of a $GDD(v=m+n,2,3;1,2)$, along with sufficient conditions for each $m\le \frac{n}{2}$. Furthermore, we introduce some construction techniques to construct some $GDD(v=m+n,2,3;1,2)$s when $m>\frac{n}{2}$, namely, a $GDD(v=9+15,2,3;1,2)$ and a $GDD(v=25+33,2,3;1,2)$.

Let $D$ be a directed graph. An anti-directed cycle in $D$ is a set of arcs which form a cycle in the underlying graph, but for which no two consecutive arcs form a directed path in $D$; this cycle is called an anti-directed Hamilton cycle if it includes all vertices of $D$. Grant [6] first showed that if $D$ has even order $n$, and each vertex indegree and outdegree in $D$ is a bit more than $\frac{2n}{3}$, then $D$ must contain an anti-directed Hamilton cycle. More recently, Busch et al. [1] lowered the lead coefficient, by showing that there must be an anti-directed Hamilton cycle if all indegrees and outdegrees are greater than $\frac{9n}{16}$, and conjectured that such a cycle must exist if all indegrees and outdegrees are greater than $\frac{n}{2}$. We prove that conjecture holds for all directed graphs of even order less than 20, and are thus able to extend the above result to show that any digraph $D$ of even order $n$ will have an anti-directed Hamilton cycle if all indegrees and outdegrees are greater than $\frac{11n}{20}$.

Let $G$ be a $(p,q)$-graph in which the edges are labeled $k,k+1,\dots ,k+q-1$, where $k\ge 0$. The vertex sum for a vertex $v$ is the sum of the labels of the incident edges at $v$. If the vertex sums are constant, modulo $p$, then $G$ is said to be $k$-edge-magic. In this paper, we investigate some classes of cubic graphs which are $k$-edge-magic. We also provide a counterexample to a conjecture that any cubic graph of order $p\equiv 2(\mathrm{mod}4)$ is $k$-edge-magic for all $k$.

In this paper, we obtain a new set of conditions which are necessary for the existence of balanced arrays of strength eight with two levels by making use of the positive semi-definiteness of the matrix of moments. We also demonstrate, using illustrative examples, that the maximum number of constraints derived using these results are better than those obtained earlier.

A set $D\subseteq V(G)$ is a dominating set of a graph $G$ if every vertex of $G$ not in $D$ is adjacent to at least one vertex in $D$. A minimum dominating set of $G$, also called a $\gamma (G)$-set, is a dominating set of $G$ of minimum cardinality. For each vertex $v\in V(G)$, we define the domination value of $v$ to be the number of $\gamma (G)$-sets to which $v$ belongs. In this paper, we find the total number of minimum dominating sets and characterize the domination values for $P_2\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n$, and $P_2\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n$.

Let $G$ be the one-point union of two cycles and suppose $G$ has $n$ edges. We show via various graph labelings that there exists a cyclic $G$-decomposition of $K_{2nt+1}$ for every positive integer $t$.

Decompositions of complete or near-complete graphs into spanning trees have been widely studied, but usually in the homogeneous case, where all component trees are isomorphic. A spanning tree decomposition $\mathcal{T}=(T_1,\dots ,T_n)$ of such a graph is purely heterogeneous if no two trees $T_i$ are isomorphic. We show existence of such decompositions with the maximum degree condition $\mathrm{\Delta }(T_i)=i+1$ for each $i\in [1..n]$, for every largest possible graph of odd order, and every even order graph which is the complement of a spanning tree satisfying a necessary maximum degree condition.

Let $G$ be a simple graph with vertex set $V(G)$ and edge set $E(G)$, and let ${\mathbb{Z}}_2=\{0,1\}$. A labeling $f:V(G)\to {\mathbb{Z}}_2$ induces a partial edge labeling $f^{\ast }:E(G)\to {\mathbb{Z}}_2$ defined by $f^{\ast }(uv)=f(u)$ if and only if $f(u)=f(v)$. For $i\in {\mathbb{Z}}_2$, let $V_f(i)=\{v\in V(G):f(v)=i\}$ and $e_f(i)=|\{e\in E(G):f^{\ast }(e)=i\}|$. A labeling $f$ is called a friendly labeling if $|V_f(0)–V_f(1)|\le 1$. The $BI(G)$, the balance index set of $G$, is defined as $\{|e_f(0)–e_f(1)|:\text{the vertex labeling }f\text{ is friendly}\}$. This paper focuses on the balance index sets of generalized book and ear expansion graphs.