The Channel Assignment Problem is often modeled by integer vertex-labelings of graphs. We will examine \(L(2,1)\)-labelings that realize the span \(\lambda\) of a simple, connected graph \(G = (V, E)\). We define the utility of \(G\) to be the number of possible expansions that can occur on \(G\), where an expansion refers to an opportunity to add a new vertex \(u\) to \(G\), with label \(\lambda(u)\), such that:

1. edges are added between \(u\) and \(v\);
2. edges are added between \(u\) and the neighbors of \(v\); and
3. the resulting labeling of the graph is a valid \(L(2, 1)\)-labeling.

Building upon results of Griggs, Jin, and Yeh, we use known values of \(\lambda\) to compute utility for several infinite families and analyze the utility of specific graphs that are of interest elsewhere.

A Sidon set \(S\) is a set of integers where the number of solutions to any integer equation \(k = k_1 + k_2\) with \(k_1, k_2 \in S\) is at most \(2\). If \(g \geq 2\), the set \(S\) is a generalized Sidon set. We consider Sidon sets modulo \(n\), where the solutions to addition of elements are considered under a given modulus. In this note, we give a construction of a generalized Sidon set modulo \(n\) from any known Sidon set.

In an ordered graph \(G\), a set of vertices \(S\) with a pre-coloring of the vertices of \(S\) is said to be a greedy defining set (GDS) if the greedy coloring of \(G\) with fixed colors of \(S\) yields a \(\chi(G)\)-coloring of \(G\). This concept first appeared in [M. Zaker, Greedy defining sets of graphs, Australas. J. Combin, 2001]. The smallest size of any GDS in a graph \(G\) is called the greedy defining number of \(G\). We show that determining the greedy defining number of bipartite graphs is an NP-complete problem, affirmatively answering a problem mentioned in a previous paper. Additionally, we demonstrate that this number for forests can be determined in linear time. Furthermore, we present a method for obtaining greedy defining sets in Latin squares and, using this method, show that any \(n \times n\) Latin square has a GDS of size at most \(n^2 – (n \log 4n)/4\).

Multi-receiver authentication codes allow one sender to construct an authenticated message for a group of receivers such that each receiver can verify authenticity of the received message. In this paper, we construct one multi-receiver authentication codes from pseudo-symplectic geometry over finite fields. The parameters and the probabilities of deceptions of this codes are also computed.

Resistance distance was introduced by Klein and Randic as a generalization of the classical distance. The Kirchhoff index \(Kf(G)\) of a graph \(G\) is the sum of resistance distances between all pairs of vertices. In this paper, we determine the bicyclic graph of order \(n \geq 8\) with maximal Kirchhoff index. This improves and extends an earlier result by Zhang \(et\; al. [19]\).

Bereg and Wang defined a new class of highly balanced \(d\)-ary trees which they call \(k\)-trees; these trees have the interesting property that the internal path length and thus the Wiener index can be calculated quite easily. A \(k\)-tree is characterized by the property that all levels, except for the last \(k\) levels, are completely filled. Bereg and Wang claim that the number of \(k\)-trees is exponentially increasing, but do not give an asymptotic formula for it. In this paper, we study the number of \(d\)-ary \(k\)-trees and the number of mutually non-isomorphic \(d\)-ary \(k\)-trees, making use of a technique due to Flajolet and Odlyzko.

A group \(G\) is said to be a \(B_k\)-group if for any \(k\)-subset \(\{a_1, \ldots, a_k\}\) of \(G\), \(\left|\{a_ia_j \mid 1 \leq i, j \leq k\}\right| \leq \frac{k(k+1)}{2}\). In this paper, a complete classification of \(B_5\)-groups is given.

For a simple undirected graph \(G = (V, E)\), a subset \(I\) of \(V(G)\) is said to be an independent set of \(G\) if any two vertices in \(I\) are not adjacent in \(G\). A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we survey the largest to fourth largest numbers of maximal independent sets among all trees and forests. In addition, we further look into the problem of determining the fifth largest number of maximal independent sets among all trees and forests. Extremal graphs achieving these values are also given.

Ruskey and Savage posed the question: For \(n \geq 2\), does every matching in \(Q_n\) extend to a Hamiltonian cycle in \(Q_n\)? Fink showed that the answer is yes for every perfect matching, thereby proving Kreweras’ conjecture. In this paper, we prove that for \(n \geq 3\), every matching in \(Q_n\) not covering exactly two vertices at distance \(3\) extends to a Hamiltonian cycle in \(Q_n\). An edge in \(Q_n\) is an \(i\)-edge if its endpoints differ in the \(i\)th position. We also show that for \(n \geq 2\), every matching in \(Q_n\) consisting of edges in at most four types extends to a Hamiltonian cycle in \(Q_n\).