We give necessary and sufficient conditions for the existence of a decomposition of the complete graph into stars which admits either a cyclic or a rotational automorphism.

This paper deals with combinatorial aspects of designs for two-way elimination of heterogeneity for making all possible paired comparisons of treatments belonging to two disjoint sets of treatments. Balanced bipartite row-column (BBPRC) designs have been defined which estimate all the elementary contrasts involving two treatments one from each of the two disjoint sets with the same variance. General efficiency balanced row-column designs (GEBRC) are also defined. Some general methods of construction of BBPRC designs have been given using the techniques of reinforcement, deletion (addition) of column or row structures, merging of treatments, balanced bipartite block (BBPB) designs, juxtaposition, etc. Some methods of construction give GEBRC designs also.

A critical set in a Latin square of order \(n\) is a set of entries in a Latin square which can be embedded in precisely one Latin square of order \(n\). Also, if any element of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order \(n\). In this paper, we find smallest weak and smallest totally weak critical sets for all the Latin squares of orders six and seven. Moreover, we computationally prove that there is no (totally) weak critical set in the back circulant Latin square of order five and we find a totally weak critical set of size seven in the other main class of Latin squares of order five.

In this paper, we give the following labelings:

1. Elegant labelings of triangular snakes \(\Delta_{n}\) , \(n \equiv 0,1,2 \mod 4\).
2. Near-elegant labeling of triangular snakes \(\Delta_{n}\) when \(n \equiv 3 \mod 4\), which are not elegant.
3. Elegant and near-elegant labelings of some of the theta graphs \(\theta_{n,n}\) when \(n = 1, 2, 3\).
4. Harmonious labelings of helms \(H_n\) when \(n\) is even.

A linear \([n,k,d]_q\) code \(C\) is called NMDS if \(d(C) = n – k\) and \(d(C^{\perp}) = k\). In this paper, the classification of the \([n,3,n-k]_q\) NMDS codes is given for \(q = 7,8,9\). It has been found using the correspondence between \([n,3,n-k]_q\) NMDS codes and \((n,3)\)-arcs of \(\mathrm{PG}(2,q)\).

A path in a digraph is antidirected if the two adjacent edges of the path have opposing orientations. In this paper, we give a necessary and sufficient condition for the edges of the complete symmetric graph to be decomposed into isomorphic antidirected paths.

The aim of this note is to provide a programme for the Computer Algebra package MAGMA, which is suitable to decode one-point Goppa codes defined from Hermitian curves.

In this article, the intersection problem for twin bowtie and near bowtie systems is completely solved.

Given a graph, a no-hole \(2\)-distant coloring (also called \(N\)-coloring) is a function \(f\) that assigns to each vertex a non-negative integer (color) such that the separation of the colors of any pair of adjacent vertices must be at least \(2\), and all the colors used by \(f\) form a consecutive set (the no-hole assumption). The minimum consecutive \(N\)-span of \(G\), \(csp(G)\), is the minimum difference of the largest and the smallest colors used in an \(N\)-coloring of \(G\), if there exists such a coloring; otherwise, define \(csp(G) = \infty\). Here we investigate the exact values of \(csp(G)\) for unit interval graphs (also known as \(1\)-unit sphere graphs). Earlier results by Roberts [18] indicate that if \(G\) is a unit interval graph on \(n\) vertices, then \(csp_1(G)\) is either \(2\chi(G) – 1\) or \(2\chi(G) – 2\), if \(n > 2\chi(G) – 1\); \(csp_1(G) = \infty\), if \(n < 2\chi(G) – 1\), where \(\chi(G)\) denotes the chromatic number. We show that in the former case (when \(n > 2\chi(G) – 1\)), both values of \(csp_1(G)\) are attained, and give several families of unit interval graphs such that \(csp_1(G) = 2\chi(G) – 2\). In addition, the exact values of \(csp_1(G)\) are completely determined for unit interval graphs with \(\chi(G) = 3\).

Let \(G\) be a graph. Let \(\gamma\) denote the minimum cardinality of a dominating set in \(G\). Let \(\beta\), respectively \(i\), denote the maximum, respectively minimum, cardinality of a maximal independent set in \(G\). We show \(\gamma + \Delta \geq \left\lceil {2\sqrt{n}-1} \right\rceil\), where \(n\) is the number of vertices of \(G\). A straightforward construction shows that given any \(G’\) there exists a graph \(G\) such that \(\gamma(G) + \Delta(G) = \left\lceil {2\sqrt{n}-1} \right\rceil\) and \(G’\) is an induced subgraph of \(G\), making classification of these \(\gamma+\Delta\) minimum graphs difficult.

We then focus on the subclass of these graphs with the stronger condition that \(\beta + \Delta = \left\lceil {2\sqrt{n}-1} \right\rceil\). For such graphs \(i = \beta\) and thus the graphs are well-covered. If \(G\) is a graph with \(\beta + \Delta = \left\lceil {2\sqrt{n}-1} \right\rceil\), we have \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\). We give a catalogue of all well-covered graphs with \(\Delta \leq 3\) and \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\). Again we establish that given any \(G’\) we can construct \(G\) such that \(G’\) is an induced subgraph of \(G\) and \(G\) satisfies \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\). In fact, the graph \(G\) can be constructed so that \(\beta(G) + \Delta(G) = \left\lceil {2\sqrt{n}-1} \right\rceil\). We remark that \(\Delta(G)\) may be much larger than \(\Delta(G’)\).

We conclude the paper by analyzing integer solutions to \(\left\lceil \frac{n}{\Delta+1} \right\rceil + \Delta = \left\lceil {2\sqrt{n}-1} \right\rceil\). In particular, for each \(n\), the values of \(\Delta\) that satisfy the equation form an interval. When \(n\) is a perfect square, this interval contains only one value, namely \(\sqrt{n}\). For each \((n, \Delta)\) solution to the equation, there exists a graph \(G\) with \(n\) vertices, maximum degree \(\Delta\), and \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\).

We construct a family of \(p-1\) square \(p \times p\) matrices (\(p\) is any prime) whose periodic cross-correlation values are uniformly \(-p, 0, +p\) between all pairs of the matrices in the family. For every one of the matrices in the family, all the off-peak autocorrelation values are \(-p\) and \(0\), while the single peak value is \(p(p-1)\). For \(p = 127\) (where the values \(-p, 0, +p\) are below \(1\%\) of the size \(p^2\) of the matrices) utilization of this construction has resulted in the superimposed embedding of twelve of the matrices (as watermarks) in the standard image “Lenna” and their subsequent retrieval without recourse to the unmarked image.

Let \(D\) be a connected symmetric digraph, \(\Gamma\) a group of automorphisms of \(D\), and \(A\) a finite abelian group with some specified property. We discuss the number of isomorphism classes of \(g\)-cyclic \(A\)-covers of \(D\) with respect to a group \(\Gamma\) of automorphisms of \(D\). Furthermore, we enumerate the number of \(I\)-isomorphism classes of \(g\)-cyclic \(\mathbb{Z}_{2^m}\)-covers of \(D\) for the cyclic group \(\mathbb{Z}_{2^m}\) of order \(2^m\), where \(I\) is the trivial subgroup of \(Aut(D)\).

We characterize tough-maximum graphs, that is, graphs having maximum number of edges among all graphs with given number of vertices and toughness.

The toughness \(t(G)\) of a noncomplete graph \(G\) is defined as

\[t(G) = \min \left\{ \frac{|S|}{\omega(G – S)} \mid S \subset V(G), \omega(G – S) \geq 2 \right\},\]

where \(\omega(G – S)\) is the number of components of \(G – S\). We also define \(t(K_n) = +\infty\) for every \(n\).

The total graph \(T(G)\) of a graph \(G\) is the graph whose vertex set can be put in one-to-one correspondence with the set \(V(G) \cup E(G)\) such that two vertices of \(T(G)\) are adjacent if and only if the corresponding elements of \(G\) are adjacent or incident.

In this article, we study the toughness of the total graph \(T(G)\) of a graph \(G\) on at least \(3\) vertices and give especially that \(t(T(G)) = t(G)\) if \(\kappa(G) = \lambda(G)\) and \(\kappa(G) \leq 2\), where \(\kappa(G)\) and \(\lambda(G)\) are the vertex and the edge-connectivity of \(G\), respectively.

We shall consider a problem of finding an ‘optimum’ tree which is closely related to the network flow problem proposed by Ford and Fulkerson, and call the solution to this problem a lexicographically optimum traffic tree (LOTT). Before examining this problem in detail, we shall review the problem of finding an optimum requirement spanning tree (ORST) studied by Hu, which is also related to the network flow problem. We can regard the LOTT problem as a min-max problem and the ORST problem as a min-sum problem. It shall be shown that, while LOTTs and ORSTs coincide completely without maximum degree constraints, they do not always coincide with the constraints. Further, we shall show that LOTTs can be expressed by simple recursion in a special case.

It is well known that some graph-theoretic extremal questions play a significant role in the investigation of communication network vulnerability. Answering questions concerning the realizability of graph invariants also solves several of these extremal problems. We define a \((p, q, \kappa, \Delta)\) graph as a graph having \(p\) points, \(q\) lines, point connectivity \(\kappa\) and maximum degree \(\Delta\). An arbitrary quadruple of integers \((a, b, c, d)\) is called \((p, q, \kappa, \Delta)\) realizable if there is a \((p, q, \kappa, \Delta)\) graph with \(p = a, q = b, \kappa = c\) and \(\Delta = d\). Necessary and sufficient conditions for a quadruple to be \((p, q, \kappa, \Delta)\) realizable are derived. In earlier papers, Boesch and Suffel gave necessary and sufficient conditions for \((p, q, \kappa)\), \((p, q, \lambda)\), \((p, q, \delta)\), \((p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability, where \(\lambda\) denotes the line connectivity of a graph and \(\delta\) denotes the minimum degree for all points in a graph.

We introduce the concept of a free \(a\)-valuation of a graph, and prove that the vertex-disjoint union of any collection of graphs with free \(\alpha\)-valuations has an \(\alpha\)-valuation. Many bipartite graphs have free \(\alpha\)-valuations, including the complete bipartite graph \(K_{m,n}\) when \(m > 1\) and \(n > 2\), and the \(d\)-cube \(Q_d\) for \(d > 2\).

Let \(G\) be a \(2\)-connected simple graph with order \(n\) (\(n \geq 5\)) and minimum degree \(5\). This paper proves that if for any two vertices \(u,v\) of \(G\) at distance two there holds \(|N(u) \bigcup N(v)| \geq n – \delta\), then \(G\) is vertex-pancyclic with a few exceptions.

Various \(n\)-color restricted partition functions are studied. Two different \(n\)-color analogues of the Gaussian polynomials are given.

There is a lexicographic ordering of \((0, 1)\)-tuples. Thus, the rows of a \((0, 1)\)-matrix can be ordered lexicographically decreasing from the top by permutations, or analogously the columns from the left. It is shown that \((0, 1)\)-matrices allow a simultaneous ordering of the rows and the columns. Those matrices are called doubly ordered, and their structure is determined. An answer is given to the question of whether a \((0, 1)\)-matrix can be transformed into a block diagonal matrix by permutations of the rows and the columns; in fact, the double ordering of a \((0, 1)\)-matrix already displays the finest block diagonal structure. Moreover, fast algorithms are presented that double order a \((0, 1)\)-matrix.

In this paper, we show that a graph \(G\) with \(e \geq 6\) edges contains at most \(\frac{h(h-1)(h-2)(h-3)}{2}\) paths of length three, where \(h \geq 0\) satisfies \(\frac{h(h-1)}{2} = e\). It follows immediately that \(G\) contains at most \(\frac{h(h-1)(h-2)(h-3)}{8}\) cycles of length four. For \(e > 6\), the bounds will be attained if and only if \(h\) is an integer and \(G\) is the union of \(K_h\) and isolated vertices. The bounds improve those found recently by Bollobás and Sarkar.

Let \(p > 2\) be a prime, and \(G = C_{p^{e_1}} \oplus \ldots \oplus C_{p^{e_k}}\) (\(1 \leq e_1 \leq \cdots \leq e_k\)) a finite abelian \(p\)-group. We prove that \(1 + 2\sum_{i=1}^{k}(p^{e_i} – 1)\) is the smallest integer \(t\) such that every sequence of \(t\) elements in \(G\) contains a zero-sum subsequence of odd length. As a consequence, we derive that if \(p^{e_k} \geq 1 + \sum_{i=1}^{k-1} (p^{e_i} – 1)\), then every sequence of \(4p^{e_k} – 3 + 2\sum_{i=1}{k-1} (p^{e_i} – 1)\) elements in \(G\) contains a zero-sum subsequence of length \(p^{e_k}\).

Solutions for the edge-isoperimetric problem on the graphs of the triangular and hexagonal tessellations of the Euclidean plane are given. The proofs are based on the fact that their symmetry group is Coxeter. In each case, there is a certain nice quotient of the stability order of the graph (which is itself a quotient of the Bruhat order of the Coxeter group by a parabolic subgroup).

For a graph \(G = (V,E)\), a set \(S \subseteq V\) is \(total\; irredundant\) if for every vertex \(v \in V\), the set \(N[v]- N[S – \{v\}]\) is not empty. The \(total \;irredundance\; number\) \(ir_t(G)\) is the minimum cardinality of a maximal total irredundant set of \(G\). We study the structure of the class of graphs which do not have any total irredundant sets; these are called \(ir_t(0)\)-graphs. Particular attention is given to the subclass of \(ir_t(0)\)-graphs whose total irredundance number either does not change (stable) or always changes (unstable) under arbitrary single edge additions. Also studied are \(ir_t(0)\)-graphs which are either stable or unstable under arbitrary single edge deletions.

Let \(n_1, n_2, \ldots, n_k\) be integers of at least two. Johansson gave a minimum degree condition for a graph of order exactly \(n_1 + n_2 + \cdots + n_k\) to contain \(k\) vertex-disjoint paths of order \(n_1, n_2, \ldots, n_k\), respectively. In this paper, we extend Johansson’s result to a corresponding packing problem as follows. Let $G$ be a connected graph of order at least \(n_1 + n_2 + \cdots + n_k\). Under this notation, we show that if the minimum degree sum of three independent vertices in \(G\) is at least:

\[3(\lfloor \frac{n_1}{2}\rfloor+\lfloor \frac{n_2}{2}\rfloor+ \ldots +\lfloor \frac{n_k}{2}\rfloor)\]

then \(G\) contains \(k\) vertex-disjoint paths of order \(n_1, n_2, \ldots, n_k\), respectively, or else \(n_1 = n_2 = \cdots = n_e = 3\), or \(k = 2\) and \(n_1 = n_2 = \text{odd}\). The graphs in the exceptional cases are completely characterized. In particular, these graphs have more than \(n_1 + n_2 + \cdots + n_k\) vertices.

In this work, first, we present sufficient conditions for a bipartite digraph to attain optimum values of a stronger measure of connectivity, the so-called superconnectivity. To be more precise, we study the problem of disconnecting a maximally connected bipartite (di)graph by removing nontrivial subsets of vertices or edges. Within this framework, both an upper-bound on the diameter and Chartrand type conditions to guarantee optimum superconnectivities are obtained. Secondly, we show that if the order or size of a bipartite (di)graph is small enough then its vertex connectivity or edge-connectivity attain their maximum values. For example, a bipartite digraph is maximally edge-connected if \(\delta^+(x)+\delta^+(y)\geq \lceil\frac{n+1}{2}\rceil\) for all pair of vertices \(x, y\) such that \(d(x,y) \geq 4\). This result improves some conditions given by Dankelmann and Volkmann in [12] for the undirected case.