We consider a discrete-time dynamic problem in graphs in which the goal is to maintain a dominating set over an infinite sequence of time steps. At each time step, a specified vertex in the current dominating set must be replaced by a neighbor. In one version of the problem, the only change to the current dominating set is replacement of the specified vertex. In another version of the problem, other vertices in the dominating set can also be replaced by neighbors. A variety of results are presented relating these new parameters to the eternal domination number, domination number, and independence number of a graph.

The Turán number $ex(m,G)$ of the graph $G$ is the maximum number of edges of an $m$-vertex simple graph having no $G$ as a subgraph. A \emph{star} $S_r$ is the complete bipartite graph $K_{1,r}$ (or a tree with one internal vertex and $r$ leaves) and $p{S}_r$ denotes the disjoint union of $p$ copies of $S_r$. A result of Lidický et al. (Electron. J. Combin. $20(2)(2013)P62$) implies that $ex(m,p{S}_r)=\lfloor \frac{(m-p+1)(r-1)}{2}\rfloor +(p-1)m–(\genfrac{}{}{0ex}{}{p}{2})$ for $m$ sufficiently large. In this paper, we give another proof and show that $ex(m,p{S}_r)=\lfloor \frac{(m-p+1)(r-1)}{2}\rfloor +(p-1)m–(\genfrac{}{}{0ex}{}{p}{2})$ for all $r\ge 1$, $p\ge 1$, and $m\ge \frac{1}{2}{r}^{2}p(p–1)+p–2+max\{rp,r^2+2r\}$.

Following a problem introduced by Schurch [M. Schurch, $OntheDepressionofGraphs$, Doctoral Dissertation, University of Victoria, 2013], we find exact values of the minimum number of colours required to properly edge colour $K_n$, $n\ge 6$, using natural numbers, such that the length of a shortest maximal path of increasing edge labels is equal to three. This result improves the result of Breytenbach and Mynhardt [A. Breytenbach and C. M. Mynhardt, On the $\epsilon$-to appear-Ascent Chromatic Index of Complete Graphs, $Involve$, to appear].

A tree $T$, in an edge-colored graph $G$, is called a $rainbowtree$ if no two edges of $T$ are assigned the same color. A $k$-$rainbowcoloring$ of $G$ is an edge coloring of $G$ having the property that for every set $S$ of $k$ vertices of $G$, there exists a rainbow tree $T$ in $G$ such that $S\subseteq V(T)$. The minimum number of colors needed in a $k$-rainbow coloring of $G$ is the $k$-$rainbowindex$ of $G$, denoted by ${\text{rx}}_k(G)$. In this paper, we investigate the $3$-rainbow index ${\text{rx}}_3(G)$ of a connected graph $G$. For a connected graph $G$, it is shown that a sharp upper bound of ${\text{rx}}_3(G)$ is ${\text{rx}}_3(G[D])+4$, where $D$ is a connected 3-way dominating set and a connected 2-dominating set of $G$. Moreover, we determine a sharp upper bound for $K_{s,t}$ ($3\le s\le t$) and a better bound for $(P_5,C_5)$-free graphs, respectively. Finally, a sharp bound for the $3$-rainbow index of general graphs is obtained.

A graph $G$ admits an $H$-covering if every edge in $E(G)$ belongs to a subgraph of $G$ isomorphic to $H$. The graph $G$ is said to be $H$-magic if there exists a bijection $f$ from $V(G)\cup E(G)$ to $\{1,2,\dots ,|V(G)|+|E(G)|\}$ such that for every subgraph $H^{\prime }$ of $G$ isomorphic to $H$, $\sum _{v\in V(H^{\prime })}f(v)+\sum _{e\in E(H^{\prime })}f(e)$ is constant. When $f(V(G))=\{1,2,\dots ,|V(G)|\}$, then $G$ is said to be $H$-supermagic. In this paper, we investigate path-supermagic cycles. We prove that for two positive integers $m$ and $t$ with $m>t\ge 2$, if $C_m$ is $P_t$-supermagic, then $C_{3m}$ is also $P_t$-supermagic. Moreover, we show that for $t\in \{3,4,9\}$, $C_n$ is $P_t$-supermagic if and only if $n$ is odd with $n>t$.

Let $G$ be an edge-colored connected graph. A path $P$ is a proper path in $G$ if no two adjacent edges of $P$ are colored the same. If $P$ is a proper $u$ — $v$ path of length $d(u,v)$, then $P$ is a proper $u$ — $v$ geodesic. An edge coloring $c$ is a proper-path coloring of a connected graph $G$ if every pair $u,v$ of distinct vertices of $G$ are connected by a proper $u$ — $v$ path in $G$ and $c$ is a strong proper coloring if every two vertices $u$ and $v$ are connected by a proper $u$ — $v$ geodesic in $G$. The minimum number of colors used in a proper-path coloring and strong proper coloring of $G$ are called the proper connection number $\text{pc}(G)$ and strong proper connection number $\text{spc}(G)$ of $G$, respectively. These concepts are inspired by the concepts of rainbow coloring, rainbow connection number $\text{rc}(G)$, strong rainbow coloring, and strong connection number $\text{src}(G)$ of a connected graph $G$. The numbers $\text{pc}(G)$ and $\text{spc}(G)$ are determined for several well-known classes of graphs $G$. We investigate the relationship among these four edge colorings as well as the well-studied proper edge colorings in graphs. Furthermore, several realization theorems are established for the five edge coloring parameters, namely $\text{pc}(G)$, $\text{spc}(G)$, $\text{rc}(G)$, $\text{src}(G)$ and the chromatic index of a connected graph $G$.

We are given suppliers and customers, and a set of tables. Every evening of the forthcoming days, there will be a dinner. Each customer must eat with each supplier exactly once, but two suppliers may meet at most once at a table. The number of customers and the number of suppliers who can sit together at a table are bounded above by fixed parameters. What is the minimum number of evenings to be scheduled in order to reach this objective? This question was submitted by a firm to the Junior company of a French engineering school some years ago. Lower and upper bounds are given in this paper, as well as proven optimal solutions with closed-form expressions for some cases.

In this paper, we mainly discuss the monotonicity of some sequences related to the hyperfibonacci sequences $\{F_n^{[r]}{\}}_{n\ge 0}$ and the hyperlucas sequences $\{L_n^{[r]}{\}}_{n\ge 0}$, where $r$ is a positive integer. We prove that $\{\sqrt[n]{F_n^{[1]}}{\}}_{n\ge 1}$ and $\{\sqrt[n]{F_n^{[2]}}{\}}_{n\ge 1}$ are unimodal and $\{\sqrt[n]{L_n^{[1]}}{\}}_{n\ge 1}$, $\{\sqrt[n]{F_{n+1}^{[1]}/F_n^{[1]}}{\}}_{n\ge 1}$, and $\{\sqrt[n]{L_{n+1}^{[1]}/L_n^{[1]}}{\}}_{n\ge 2}$ are decreasing. Furthermore, we discuss the monotonicity of the sequences

$${\left\{\frac{\sqrt[n+1]{F_{n+1}^{[1]}}}{\sqrt[n]{F_n^{[1]}}}\right\}}_{n\ge 1}\text{ and }{\left\{\frac{\sqrt[n+1]{L_{n+1}^{[1]}}}{\sqrt[n]{L_n^{[1]}}}\right\}}_{n\ge 1}$$

The Ramsey number $R(C_4,K_m)$ is the smallest $n$ such that any graph on $n$ vertices contains a cycle of length four or an independent set of order $m$. With the help of computer algorithms, we obtain the exact values of the Ramsey numbers $R(C_4,K_9)=30$ and $R(C_4,K_{10})=36$. New bounds for the next two open cases are also presented.

We describe the construction of transitive $2$-designs and strongly regular graphs defined on the conjugacy classes of the maximal and second maximal subgroups of the symplectic group $S(6,2)$. Furthermore, we present linear codes invariant under the action of the group $S(6,2)$ obtained as the codes of the constructed designs and graphs.

Gionfriddo and Lindner detailed the idea of the metamorphosis of $2$-fold triple systems with no repeated triples into $2$-fold $4$-cycle systems of all orders where each system exists in [3]. In this paper, this concept is expanded to address all orders $n$ such that $n\equiv 5,8,\text{ or }11(\mathrm{mod}12)$. When $n\equiv 11(\mathrm{mod}12)$, a maximum packing of $2K_n$ with triples has a metamorphosis into a maximum packing of $2K_n$ with $4$-cycles, with the leave of a double edge being preserved throughout the metamorphosis. For $n\equiv 5\text{ or }8(\mathrm{mod}12)$, a maximum packing of $2K_n$ with triples has a metamorphosis into a $2$-fold $4$-cycle system of order $n$, except for when $n=5\text{ or }8$, when no such metamorphosis is possible.

Eternal domination of a graph requires the positioning of guards to protect against an infinitely long sequence of attacks where, in response to an attack, each guard can either remain in place or move to a neighbouring vertex, while keeping the graph dominated. This paper investigates the $m$-eternal domination numbers for $5\times n$ grid graphs. The values, previously known for $1\le n\le 5$, are determined for $6\le n\le 12$, and lower and upper bounds derived for $n>12$.

A graph $G=(V,E)$ with $p$ vertices and $q$ edges is said to be odd graceful if there is an injection $f$ from the vertex set of $G$ to $\{0,1,2,\dots ,2q–1\}$ such that when each edge $xy$ is assigned the label $|f(x)–f(y)|$, the resulting edge labels are distinct and induce the set $\{1,3,5,\dots ,2q–1\}$. In 2009, Barrientos conjectured that every bipartite graph is odd graceful. In this paper, we partially solve Barrientos’ conjecture by showing that the following graphs are odd graceful:

1. Finite union of paths, stars, and caterpillars;
2. Finite union of ladders;
3. Finite union of paths, bistars, and caterpillars;
4. The coronas $K_{m,n}\odot K_1$; and
5. Finite union of graphs obtained by one endpoint union of an odd number of paths of uniform length.

In this paper, $q$-analogs of covering designs and Steiner systems based on the subspaces of type $(m,0)$ and the subspaces of type $(m_1,0)$ in singular linear space ${\mathbb{F}}_q^{(n+l)}$ over ${\mathbb{F}}_q$ are presented, where $m_1<m$. Then the properties about $q$-analogs of covering designs and Steiner systems are discussed.

Let $G$ be a graph with $q$ edges. A graph $G^{\ast }$ is called an arbitrary supersubdivision of $G$ if $G^{\ast }$ is obtained from $G$ by replacing every edge $e_i$ of $G$ by a complete bipartite graph $K_{2,m_i}$, such a way that the end vertices of each $e_i$ are identified with the two vertices of the 2-vertices part of $K_{2,m_i}$, after removing the edge $e_i$ from $G$, where $m_i$ of $K_{2,m_i}$ may vary arbitrarily for each edge $e_i$, $1\le i\le q$.

As recognition of cordial graph is an NP-complete, it is interesting and significant to find the graphs whose arbitrary supersubdivision graphs are cordial. In this paper, we show that arbitrary supersubdivision of every bipartite graph is cordial. This result is obtained as a corollary of the general result that “Almost arbitrary supersubdivision of every graph is cordial”, where almost arbitrary supersubdivision is a relaxation of arbitrary supersubdivision graph.

Let $G$ be a graph with edge set $E(G)=E_1\cup E_2$ and $E_1\cap E_2=\mathrm{\varnothing }$. A graph $G$ is called an almost arbitrary supersubdivision graph of $G$ if $G$ is obtained from $G$ by replacing every edge $e_i\in E$ by a complete bipartite graph $K_{2,m_i}$, such a way that the end vertices of each $e_i$ are merged with the two vertices of the 2-vertices part of $K_{2,m_i}$, after removing the edge $e_i$ from $G$, where $m_i$ is chosen as an arbitrary positive integer if $e_i\in E_1$ or else $m_i$ is chosen as an arbitrary even positive integer if $e_i\in E_2$.

Under the conditions looser than previous works, this paper shows that the $n$-dimensional folded hypercube networks have a cycle with length at least $2^n–2|F_v|$ when the number of faulty vertices and non-critical edges is at most $2n–4$, where $|F_v|$ is the number of faulty vertices. Meanwhile, this paper proves that $F{Q}_n$ contains a fault-free cycle with length at least $2^n–2|F_v|$, under the constraints that (1) The number of both faulty nodes and faulty edges is no more than $2n–3$ and there is at least one faulty edge; (2) every node in $F{Q}_n$ is incident to at least two fault-free links whose other end nodes are fault-free. These results have improved the present results with further theoretical evidence of the fact that $F{Q}_n$ has excellent node-fault-tolerance and edge-fault-tolerance when used as a topology of large scale computer networks.

In this paper, $(r,2,k)$-regular fuzzy graphs and totally $(r,2,k)$-regular fuzzy graphs are defined and $(r,2,k)$-regular fuzzy graphs and totally $(r,2,k)$-regular fuzzy graphs are compared through various examples. A necessary and sufficient condition under which they are equivalent is provided. Also, $(r,2,k)$-regularity on some fuzzy graphs whose underlying crisp graphs are a path on four vertices, a Barbell graph $B_{n,n}$ $(n>1)$ and a cycle is studied with some specific membership functions.

The definition of $E_k$-cordial graphs is advanced by Cahit and Yilmaz${}^{[1]}$. Based on [1], a graph $G$ is said to be $E_3$-cordial if it is possible to label the edges with the numbers from the set $\{0,1,2\}$ in such a way that, at each vertex $v$, the sum of the labels on the edges incident with $v$ modulo $3$ satisfies the inequalities $|v(i)–v(j)|\le 1$ and $|e(i)–e(j)|\le 1$, where $v(s)$ and $e(t)$ are, respectively, the number of vertices labeled with $s$ and the number of edges labeled with $t$. In [1]-[3], authors discussed the $E_3$-cordiality of $P_n$ $(n\ge 3)$; stars $S_n$, $|S_n|=n+1$; $K_n$ $(n\ge 3)$, $C_n$ $(n\ge 3)$, the one point union of any number of copies of $K_n$ and $K_m\odot K_m$. In this paper, we give the $E_3$-cordiality of $W_n$, $P_m\times P_n$, $K_{m,n}$ and trees.