A \(k\)-labeling of a graph is a labeling of the vertices of the graph by \(k\)-tuples of non-negative integers such that two vertices of \(G\) are adjacent if and only if their label \(k\)-tuples differ in each coordinate. The dimension of a graph \(G\) is the least \(k\) such that \(G\) has a \(k\)-labeling.

Lovász et al. showed that for \(n \geq 3\), the dimension of a path of length \(n\) is \((\log_2 n)^+\). Lovász et al. and Evans et al. determined the dimension of a cycle of length \(n\) for most values of \(n\). In the present paper, we obtain the dimension of a caterpillar or provide close bounds for it in various cases.

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 \(pS_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,pS_r) = \left\lfloor\frac{(m-p+1)(r-1)}{2}\right\rfloor + (p-1)m – \binom{p}{2}\) for \(m\) sufficiently large. In this paper, we give another proof and show that \(ex(m,pS_r) = \left\lfloor \frac{(m-p+1)(r-1)}{2}\right\rfloor + (p-1)m – \binom{p}{2}\) for all \(r \geq 1\), \(p \geq 1\), and \(m \geq \frac{1}{2}r^2p(p – 1) + p – 2 + \max\{rp, r^2 + 2r\}\).

Following a problem introduced by Schurch [M. Schurch, \({On\; the\; Depression\; of\; Graphs}\), Doctoral Dissertation, University of Victoria, 2013], we find exact values of the minimum number of colours required to properly edge colour \( K_n \), \( n \geq 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 \(\varepsilon\)-to appear-Ascent Chromatic Index of Complete Graphs, \({Involve}\), to appear].

A tree \( T \), in an edge-colored graph \( G \), is called a \({rainbow\; tree}\) if no two edges of \( T \) are assigned the same color. A \( k \)-\({rainbow\; coloring}\) 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 \)-\({rainbow\; index}\) 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 \leq s \leq 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’ \) of \( G \) isomorphic to \( H \), \( \sum_{v\in V(H’)} f(v) + \sum_{e\in E(H’)} 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 \geq 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\geq 0} \) and the hyperlucas sequences \( \{L_{n}^{[r]}\}_{n\geq 0} \), where \( r \) is a positive integer. We prove that \( \{\sqrt[n]{F_{n}^{[1]}}\}_{n\geq 1} \) and \( \{\sqrt[n]{F_{n}^{[2]}}\}_{n\geq 1} \) are unimodal and \( \{\sqrt[n]{L_{n}^{[1]}}\}_{n\geq 1} \), \( \{\sqrt[n]{F_{n+1}^{[1]}/{F_{n}^{[1]}}}\}_{n\geq 1} \), and \( \{\sqrt[n]{L_{n+1}^{[1]}/{L_{n}^{[1]}}}\}_{n\geq 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\geq 1} \text{ and } \left\{\frac{\sqrt[n+1]{L_{n+1}^{[1]}}}{\sqrt[n]{L_{n}^{[1]}}}\right\}_{n\geq 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.