A twofold 8-cycle system is an edge-disjoint decomposition of a twofold complete graph (which has two edges between every pair of vertices) into 8-cycles. The order of the complete graph is also called the order of the 8-cycle system. A twofold 2-perfect 8-cycle system is a twofold 8-cycle system such that the collection of distance 2 edges in each 8-cycle also cover the complete graph, forming a (twofold) 4-cycle system. Existence of 2-perfect 8-cycle systems for all admissible orders was shown in [1], although \(\lambda\)-fold existence for \(\lambda > 1\) has not been done.

In this paper, we impose an extra condition on the twofold \(2\)-perfect \(8\)-cycle system. We require that the two paths of length two between each pair of vertices, say \(x, a_{xy}, y\) and \(x, b_{xy}, y\), should be distinct, that is, with \(a_{xy} \neq b_{xy}\); thus they form a \(4\)-cycle \((x, a, y, b)\).

We completely solve the existence of such twofold 2-perfect 8-cycle systems with this “extra” property. All admissible orders congruent to $0$ or 1 modulo 8 can be achieved, apart from order 8.

We consider a storage/scheduling problem which, in addition to the standard restriction involving pairs of elements that cannot be placed together, considers pairs of elements that must be placed together. A set \( S \) is a colored-independent set if, for each color class \( V_i \), \( S \cap V_i = V_i \) or \( S \cap V_i = \emptyset \). In particular, \( \beta_{\mathrm{PRT}}(G) \), the independence-partition number, is determined for all paths of order \( n \). Finally, we show that the resulting decision problem for graphs is NP-complete even when the input graph is a path.

Given a partition \(\{P_1, \ldots, P_m\}\) of a \(v\)-set, a restricted simple \(1\)-design is a collection of distinct subsets (blocks) such that every element occurs in the same number of blocks, but any two elements from the same part do not occur together in the same block. We give a construction of restricted simple \(1\)-designs to show that the necessary conditions are sufficient for the existence of restricted simple \(1\)-designs.

An \((r, \lambda)\) overlap coloring of a graph \( G \) allocates \( r \) colors to each vertex subject to the condition that any pair of adjacent vertices shares exactly \( \lambda \) colors. The \((r, \lambda)\) overlap chromatic number of \( G \) is the least number of colors required for such a coloring. The overlap chromatic numbers of bipartite graphs are easy to find; those of odd cycle graphs have already been established. In this paper, we find the overlap chromatic numbers of the wheel graphs.

A family \(\mathcal{G}\) of connected graphs is a family with constant metric dimension if \(\dim(\mathcal{G})\) is finite and does not depend upon the choice of \(G\) in \(\mathcal{G}\).

The metric dimension of some classes of convex polytopes has been determined in \([8-12]\) and an open problem was raised in \([10]\): \emph{Let \(G\) be the graph of a convex polytope which is obtained by joining the graph of two different convex polytopes \(G_1\) and \(G_2\) (such that the outer cycle of \(G_1\) is the inner cycle of \(G_2\)) both having constant metric dimension. Is it the case that \(G\) will always have the constant metric dimension?}

In this paper, we study the metric dimension of an infinite class of convex polytopes which are obtained by the combinations of two different graphs of convex polytopes. It is shown that this infinite class of convex polytopes has constant metric dimension and only three vertices chosen appropriately suffice to resolve all the vertices of these classes of convex polytopes.

One natural extension of classical Ramsey numbers to multipartite graphs is to consider 2-colorings of the complete multipartite graph consisting of \( n \) parts, each of size \( k \), denoted \( K_{n \times k} \). We may then ask for the minimum integer \( n \) such that \( K_{n \times k} \rightarrow (G, H) \) for two given graphs \( G \) and \( H \). We study this number for the cases when \( G \) and \( H \) are paths or cycles and show some general bounds and relations to classical Ramsey theory.

By means of the \( q \)-finite differences and the derivative operator, we derive, from an alternating \( q \)-binomial sum identity with a free variable \( x \), several interesting identities concerning the generalized \( q \)-harmonic numbers.

In [A.G. Chetwynd and A.J.W. Hilton, Critical star multigraphs, Graphs and Combinatorics 2 (1986), 209-221] Chetwynd and Hilton started the investigations of the edge-chromatic properties of a particular class of multigraphs, which they called star multigraphs. A star multigraph is a multigraph such that there exists a vertex \(v^*\) that is incident with each multiple edge. Star multigraphs turn out to be useful tools in the study of the chromatic index of simple graphs.
The main goal of this paper is to provide shorter and simpler proofs of all the main theorems contained in the above mentioned paper. Most simplifications are achieved by means of a formula for the chromatic index recently obtained by the author and by a careful use of arguments involving fans.

Broadcasting is the process of message transmission in a communication network. The communication network is modeled by a graph \( G = (V, E) \), where the set of vertices \( V \) represents the network members and the set of edges \( E \) represents the communication links between two given vertices. We assume that \( G \) is connected and undirected. One vertex, called the \emph{originator} of the graph, holds a message that has to be transmitted to all vertices of the network by placing a series of calls over the network.

A \textbf{k-port} line broadcasting in \( G \) is a model in which an informed vertex can call, at each time unit, at most \( k \) vertices and transmit a message through a path, as long as two transmissions do not use the same edge at the same time. In case \( k \) is not bounded, the model is called the all-port line model.

In this paper, we extend Cohen’s work \([6]\), which handles the all-port line model.

In this paper we consider 1-movable dominating sets, motivated by the use of sensors employed to detect certain events in networks, where the sensors have a limited ability to react under changing conditions in the network. A 1-movable dominating set is a dominating set \( S \subseteq V(G) \) such that for every \( v \in S \), either \( S – \{v\} \) is a dominating set, or there exists a vertex \( u \in (V(G) – S) \cap N(v) \) such that \( (S – \{v\}) \cup \{u\} \) is a dominating set. We present computational complexity results and bounds on the size of 1-movable dominating sets in arbitrary graphs. We also give a polynomial time algorithm to find minimum 1-movable dominating sets for trees. We conclude by extending this idea to \( k \)-movable dominating sets.

A vertex \( u \) in a set \( S \) of vertices of a graph \( G \) has a private neighbor (with respect to \( S \)) if either (i) \( u \) has no neighbor in \( S \) or (ii) there exists some vertex \( v \in V(G) – S \) that is a neighbor of \( u \) but not a neighbor of any other vertex in \( S \). A set \( S \) is irredundant in a graph \( G \) if every vertex in \( S \) has a private neighbor. An irredundant \( k \)-coloring of a graph \( G \) is a partition of \( V(G) \) into \( k \) irredundant sets. The minimum \( k \) for which \( G \) has an irredundant \( k \)-coloring is the irredundant chromatic number \( \chi_{ir}(G) \) of \( G \).

A complete coloring of a graph \( G \) is a proper vertex coloring of \( G \) having the property that for every two distinct colors \( i \) and \( j \) used in the coloring, there exist adjacent vertices of \( G \) colored \( i \) and \( j \). The maximum positive integer \( k \) for which \( G \) has a complete \( k \)-coloring is the achromatic number \( \psi(G) \) of \( G \).

A Grundy coloring of a graph \( G \) is a proper vertex coloring of \( G \) having the property that for every two colors (positive integers) \( i \) and \( j \) with \( i < j \), every vertex colored \( j \) has a neighbor colored \( i \). The maximum positive integer \( k \) for which a graph \( G \) has a Grundy \( k \)-coloring is the Grundy number \( \Gamma(G) \) of \( G \). The chromatic number of a graph \( G \) is denoted by \( \chi(G) \). For every graph \( G \), these four coloring parameters satisfy the inequalities \( \chi_{ir}(G) \leq \chi(G) \leq \Gamma(G) \leq \psi(G) \). It is shown that if \( a, b, c \), and \( d \) are integers with \( 2 \leq a \leq b \leq c \leq d \), then there exists a nontrivial connected graph \( G \) with \( \chi_{ir}(G) = a \), \( \chi(G) = b \), \( \Gamma(G) = c \), and \( \psi(G) = d \) if and only if \( d = 2 \) or \( c \neq 2 \).

Let \(\Sigma\) be a totally ordered set. We work on finite strings \(b = b_1 b_2 \ldots b_m\) of \(b_i\) elements from \(\Sigma\). Such a \(b\) is a Lyndon word (Lyn) if \(m \geq 1\), and \(b\) is the unique first in lexicographic order among the \(m\) rows of the \(m \times m\) circulant matrix with \(b\) as the first row.

A classic result is that every string \(b\) has a unique maximal factorization \(umf(b)\) into Lyndon words, each Lyndon word of the maximum possible size in \(b\).

In 1983, J. P. Duval \([6]\) published Algorithm 1, which finds \(umf(b)\). It was studied in 1991 by A. Apostolico and M. Crochemore \([1]\). Their work was then studied in 1994 by J.W. Daykin, C.S. Iliopoulos, and W.F. Smyth \([5]\).

Since Duval used a programming language, we start by giving a new simple account of his Algorithm 1. Our Algorithm 2 modifies Duval’s Algorithm 1 to find \(umf(a)\), when \(a\) is a string \(a = A_1 A_2 \ldots A_p\) of Lyndon words \(A_i\).

Our Algorithm 3 is also for a string \(a = A_1 A_2 \ldots A_p\) of Lyndon words \(A_i\). It is completely different from Algorithms 1 and 2. It snakes right, left, right, and so on. It revealed that Lyndon words have a special structure. We give an example where Algorithm 3 needs almost \(2m\) tests; we think that is the most needed, but cannot give a rigorous proof.

Let \(\Sigma\) be a totally ordered set. We work on finite strings \(b = b_1 b_2 \ldots b_m\) of \(b_i\) elements from \(\Sigma\). Such a \(b\) is a lyn(Lyndon word) if \(m \geq 1\), and \(b\) is the unique first in lex(lexicographic order) among the \(m\) rows of the \(m \times m\) circulant matrix with \(b\) as first row.

A classic result is that every string \(b\) has a unique max factorization \(umf(b)\) into Lyns , each Lyn of maximum possible size in \(b\).

In 1983 J. P. Duval [6] published Algorithm 1, which finds \(umf(b)\). It was studied in 1991 by A. Apostolico and M. Crochemore [1]. Then their work was studied in 1994 by J.W. Daykin, C.S. Iliopoulos, and W.F. Smyth [5].

Since Duval used a programming language, we start by giving a new simple account of his Algorithm 1. Then our Algorithm 2 given here modifies Duval’s Algorithm 1 to find \(umf(a)\), when \(a\) is a string \(a = A_1 A_2 \ldots A_p\) of Lyndon words \(A_I\).

Our Algorithm 3 is also for a string \(a = A_1 A_2 \ldots A_p\) of Lyndon words \(A_I\). It is completely different from Algorithms 1 and 2. It snakes right, left, right, and so on. It revealed the fact that Lyndon words have a special structure. We give an example where Algorithm 3 needs almost \(2m\) tests; we think that is the most needed, but cannot give a rigorous proof.

We find interesting properties of Lyns, some of which may be new.

A family \(\mathcal{G}\) of connected graphs is a family with constant metric dimension if \(\dim(G)\) is finite and does not depend upon the choice of \(G\) in \(\mathcal{G}\).

The metric dimension of some classes of plane graphs has been determined in \([3]\), \([4]\), \([5]\), \([10]\), \([13]\), and \([18]\), while the metric dimension of some classes of convex polytopes has been determined in \([8]\), and a question was raised as an open problem: Is it the case that the graph of every convex polytope has constant metric dimension? In this paper, we study the metric dimension of two classes of convex polytopes. It is shown that these classes of convex polytopes have constant metric dimension and only three vertices chosen appropriately suffice to resolve all the vertices of these classes of convex polytopes. It is natural to ask for the characterization of classes of convex polytopes with constant metric dimension.

The degree set of a graph \( G \) is the set \( S \) consisting of the distinct degrees of vertices in \( G \). In 1977, Kapoor, Polimeni, and Wall \([2]\) determined the least number of vertices among simple graphs with a given degree set. In this note, we look at the analogue problem concerning the least order and the least size of a multigraph with a given degree set.

Let \(\mathcal{P}\) be a graph property and \(G\) a graph. \(G\) is said to be \(\mathcal{P}\)-saturated if \(G\) does not have property \(\mathcal{P}\) but the addition of any edge between non-adjacent vertices of \(G\) results in a graph with property \(\mathcal{P}\). If \(\mathcal{P}\) is a bipartite graph property and \(G\) is a bipartite graph not in \(\mathcal{P}\), but the addition of any edge between non-adjacent vertices in different parts results in a graph in \(\mathcal{P}\), then \(G\) is \(\mathcal{P}\)-bisaturated. We characterize all \(\mathcal{P}\)-saturated graphs, for which \(\mathcal{P}\) is the family of interval graphs, and show that this family is precisely the family of maximally non-chordal graphs. We also present a conjectured characterization of all \(\mathcal{P}\)-bisaturated graphs, in the case where \(\mathcal{P}\) is the family of interval bigraphs, and prove it as far as current forbidden subgraph characterizations allow. We demonstrate that extremal non-interval graphs and extremal non-interval bigraphs are highly related, in that the former is simply a complete graph with \(2K_2\) removed and the latter is a complete bipartite graph with \(3K_2\) removed.

The Stein-Lovasz Theorem can be used to get existence results for some combinatorial problems using constructive methods rather than probabilistic methods. In this paper, we discuss applications of the Stein-Lovasz Theorem to some combinatorial set systems and arrays, including perfect hash families, separating hash families, splitting systems, covering designs, lotto designs and \( A \)-free systems. We also compare some of the bounds obtained from the Stein-Lovasz Theorem to those using the basic probabilistic method.

The distribution of distances in the star graph \( S_{T_n} \) (\(1 < n \in \mathbb{Z}\)) is established, and subsequently a threaded binary tree is obtained that realizes an orientation of \( S_{T_n} \) whose levels are given by the distances to the identity permutation, via a pruning algorithm followed by a threading algorithm. In the process, the distributions of distances of the efficient dominating sets of \( S_{T_n} \) are determined.