Let \(G\) be a simple graph with vertex set \(V\) and edge set \(E\). A vertex labeling \(\overline{f}: V \to \{0,1\}\) induces an edge labeling \(\overline{f}: E \to \{0,1\}\) defined by \(f(uv) = |f(u) – f(v)|\) .Let \(v_f(0),v_f(1)\) denote the number of vertices \(v\) with \(f(v) = 0\) and \(f(v) = 1\) respectively. Let \(e_f(0),e_f(1)\) be similarly defined. A graph is said to be cordial if there exists a vertex labeling \(f\) such that \(|v_f(0) – vf(1)| \leq 1\) and \(|e_f(0) – e_f(1)| \leq 1\).
A \(t\)-uniform homeomorph \(P_t(G)\) of \(G\) is the graph obtained by replacing all edges of \(G\) by vertex disjoint paths of length \(t\). In this paper we investigate the cordiality of \(P_t(G)\), when \(G\) itself is cordial. We find, wherever possible, a cordial labeling of \(P_t(G)\), whose restriction to \(G\) is the original cordial labeling of \(G\) and prove that for a cordial graph \(G\) and a positive integer \(t\), (1) \(P_t(G)\) is cordial whenever \(t\) is odd, (2) for \(t \equiv 2 \pmod{4}\) a cordial labeling \(g\) of \(G\) can be extended to a cordial labeling \(f\) of \(P_t(G)\) iff \(e_0\) is even, (3) for \(t \equiv 0 \pmod{4}\), a cordial labeling \(g\) of \(G\) can be extended to a cordial labeling \(f\) of \(P_t(G)\) iff \(e_1\) is even.
The domination graph \(dom(D)\) of a digraph \(D\) has the same vertex set as \(D\), and \(\{u,v\}\) is an edge if and only if for every \(w\), either \((u,w)\) or \((v,w)\) is an arc of \(D\). In earlier work we have shown that if \(G\) is a domination graph of a tournament, then \(G\) is either a forest of caterpillars or an odd cycle with additional pendant vertices or isolated vertices. We have also earlier characterized those connected graphs and forests of non-trivial caterpillars that are domination graphs of tournaments. We complete the characterization of domination graphs of tournaments by describing domination graphs with isolated vertices.
It is proved that the \(n\)-cone \(C_m \vee K_n^c\) is graceful for any \(n \geq 1\) and \(m = 0\) or \(3 \pmod{12}\). The gracefulness of the following \(n\)-cones is also established: \(C_4 \vee K_n^c\), \(C_5 \vee K_2^c\), \(C_7 \vee K_n^c\), \(C_9 \vee K_2^c\), \(C_{11} \vee K_n^c\), \(C_{19} \vee K_n^c\). This partially answers the question of gracefulness of \(n\)-cones which is listed as an open problem in the survey article by J.A. Gallian.
We tackle the problem of estimating the Shannon capacity of cycles of odd length. We present some strategies which allow us to find tight bounds on the Shannon capacity of cycles of various odd lengths, and suggest that the difficulty of obtaining a general result may be related to different behaviours of the capacity, depending on the “structure” of the odd integer representing the cycle length. We also describe the outcomes of some experiments, from which we derive the evidence that the Shannon capacity of odd cycles is extremely close to the value of the Lovasz theta function.
The queen’s graph \(Q_n\) has the squares of the \(n \times n\) chessboard as its vertices; two squares are adjacent if they are in the same row, column, or diagonal. Let \(\gamma(Q_n)\) be the minimum size of a dominating set of \(Q_n\). Spencer proved that \(\gamma(Q_n) \geq {(n-1)}/{2}\) for all \(n\), and the author showed \(\gamma(Q_n) = {(n-1)}/{2}\) implies \(n \equiv 3 \pmod{4}\) and any minimum dominating set of \(Q_n\) is independent.
Define a sequence by \(n_1 = 3\), \(n_2 = 11\), and for \(i > 2\), \(n_i = 4n_{i-1} – n_{i-2} – 2\). We show that if \(\gamma(Q_n) = {(n-1)}/{2}\) then \(n\) is a member of the sequence other than \(n_3 = 39\), and (counting from the center) the rows and columns occupied by any minimum dominating set of \(Q_n\) are exactly the even-numbered ones. This improvement in the lower bound enables us to find the exact value of \(\gamma(Q_n)\) for several \(n\); \(\gamma(Q_n) = {(n+1)}/{2}\) is shown here for \(n = 23, 39\), and elsewhere for \(n = 27, 71, 91, 115, 131\).
A characterization of symmetric bent functions has been presented in [3]. Here, we provide a simple proof of the same result.
We prove that the total domination number of an \(n\)-vertex claw-free cubic graph is at most \({n}/{2}\).
This paper deals with the problem of labeling the edges of a plane graph in such a way that the weight of a face is the sum of the labels of the edges surrounding that face. The paper describes \((a, d)\)-face antimagic labeling of a certain class of convex polytopes.
Below, we prove that there are exactly 244 nonisomorphic cyclic decompositions of the complete graph \(K_{25}\) into cubes. The full list of such decompositions is given in the Appendix.
The magic square is probably the most popular and well-studied topic in recreational mathematics. We investigate a variation on this classic puzzle — the antimagic square. We review the history of the problem, and the structure of the design. We then present computational results on the enumeration and construction. Finally, we describe a construction for all orders.
We establish a necessary and sufficient condition for the existence of a perfect distance-\(d\) placement in 3-dimensional tori, for both regular and irregular cases.
Let \(G\) be a simple graph and \(f\) a function from the vertices of \(G\) to the set of positive integers. An \((f, n)\)-coloring of \(G\) is an assignment of \(n\) colors to the vertices of \(G\) such that each vertex \(x\) is adjacent to less than \(f(x)\) vertices with the same color as \(x\). The minimum \(n\) such that an \((f, n)\)-coloring of \(G\) exists is defined to be the \(f\)-chromatic number of \(G\). In this paper, we address a study of this kind of locally restricted coloring.
A \(G\)-decomposition of the complete graph \(K_v\) is a set \({S}\) of subgraphs of \(K_v\), each isomorphic to \(G\), such that the edge set of \(K_v\) is partitioned by the edge sets of the subgraphs in \({S}\). For all positive integers \(v\) and every 2-regular graph \(G\) with ten or fewer vertices, we prove necessary and sufficient conditions for the existence of a \(G\)-decomposition of \(K_v\).
A broadcast graph on \(n\) vertices is a network in which a message can be broadcast in minimum possible (\(=\lceil \log_2 n \rceil\)) time from any vertex. Broadcast graphs which have the smallest number of edges are called \emph{Minimum Broadcast Graphs}, and are subjects of intensive study. In this paper, we study how the number of edges in minimum broadcast graphs decreases, as we allow additional time over \(\lceil \log_2 n \rceil\).
We improve results obtained by Shastri in [15] and prove a conjecture posed by Shastri in [15, 16].
We give a new construction for skew-Hadamard matrices. This yields new infinite families of skew-Hadamard matrices, including 43 new skew-Hadamard matrices of order \(4q < 4000\).
The binary and ternary codes spanned by the rows of the point-by-block, pair-by-block, block-by-point incidence matrices of some 2-designs of small orders and their orthogonal complements are studied. Among some results, it is shown that if the code is properly chosen, then the weight distribution of the code serves as an appropriate design isomorphism invariant. The automorphism groups of the codes and the design are computed.
A Latin square of order \(n\) is an \(n \times n\) array of cells containing one of the \(n\) elements in \(\{1,2,\ldots,n\}\) such that in each row and each column each element appears exactly once. A partial transversal \(P\) of a Latin square \(L\) is a set of \(n\) cells such that no two are in the same row and the same column. The number of distinct elements in \(P\) is referred to as the length of \(P\), denoted by \(|P|\), and the maximum length of a partial transversal in \(L\) is denoted by \(t(L)\). In this paper, we study the technique used by Shor which shows that \(t(L) \geq n – 5.53{(\ln)}^2\) and we improve the lower bound slightly by using a more accurate evaluation.
The maximum possible toughness among graphs with \(n\) vertices and \(m\) edges is considered. This is an analog of the corresponding problem regarding maximum connectivity solved by Harary. We show that, if \(m < \lceil \frac{3n}{2} \rceil\) or \(m \geq n(\lfloor \frac{n}{6} \rfloor + \lfloor \frac{n \mod 6}{3} \rfloor)\), then the maximum toughness is half of the maximum connectivity. The same conclusion is obtained if \(r = \lfloor \frac{2m}{n} \rfloor \geq 1\) and \(\frac{(n-1)(r+1)}{2} \leq m < \frac{n(r+1)}{2}\). However, maximum toughness can be strictly less than half of maximum connectivity. Some values of maximum toughness are computed for \(1 \leq n \leq 12\), and some open problems are presented
We describe a random variable \(\text{D}_\text{{n,m}}\), \(\text{n} \geq \text{m} \geq 1\), as the number of failures until the first success in a sequence of n Bernoulli trials containing exactly m successes, for which all possible sequences containing m successes and n-m failures are equally likely. We give the probability density function, the expectation, and the variance of \(\text{D}_\text{{n,m}}\). We define a random variable \(\text{D}_\text{n}\), \(\text{n} \geq 1\), to be the mean of \(\text{D}_\text{n,1}, \ldots, \text{D}_\text{n,n}\). We show that E\([\text{D}_\text{n}]\) is a monotonically increasing function of n and is bounded by \(\ln\) n. We apply these results to a practical application involving a video-on-demand system with interleaved movie files and a delayed start protocol for keeping a balanced workload.
The exact values of \(c(n)\) are determined, where \(c(n)\) denotes the largest \(k\) for which there exists a triangle-free \(k\)-regular graph on \(n\) vertices containing a cut-vertex. As a corollary, we obtain a lower bound on the densest triangle-free regular graphs of given order that do not have a one-factorization.
In the search for doubly resolvable Kirkman triple systems of order \(v\), systems admitting an automorphism of order \((v-3)/3\) fixing three elements, and acting on the remaining elements in three orbits of length \((v-3)/3\), have been of particular interest. We have established by computer that 100 such Kirkman triple systems exist for \(v=21\), 90,598 for \(v=27\), at least 4,494,390 for \(v=33\), and at least 1,626,684 for \(v=39\). This improves substantially on known lower bounds for numbers of Kirkman triple systems. We also establish that the KTS(27)s so produced yield 47 nonisomorphic doubly resolved KTS(27)s admitting the same automorphism.
In this paper, we show that for every modular lattice \(L\), if its size is at least three times its excess, then each component of its direct product decomposition is isomorphic to one of the following: a Boolean lattice of rank one \(B_1\), a chain of length two \(3\), a diamond \(M_3\), and \(M_4\), where \(M_n\) is a modular lattice of rank two which has exactly \(n\) atoms.
Using algebraic curves, it will be proven that large partial unitals can be embedded into unitals and large \((k,n)\)-arcs into maximal arcs.
In a set equipped with a binary operation, \((S, \cdot)\), a subset \(U\) is defined to be avoidable if there exists a partition \(\{A, B\}\) of \(S\) such that no element of \(U\) is the product of two distinct elements of \(A\) or of two distinct elements of \(B\). For more than two decades, avoidable sets in the natural numbers (under addition) have been studied by renowned mathematicians such as Erdős, and a few families of sets have been shown to be avoidable in that setting. In this paper, we investigate the generalized notion of an avoidable set and determine the avoidable sets in several families of groups; previous work in this field considered only the case \((S, \cdot) = (\mathbb{N}, +)\).
This paper studied the problems of counting independent sets, maximal independent sets, and maximum independent sets of a graph from an algorithmic point of view. In particular, we present linear-time algorithms for these problems in trees and unicyclic graphs.
The Stirling numbers of first kind and Stirling numbers of second kind, denoted by \(s(n,k)\) and \(S(n,k)\) respectively, arise in a variety of combinatorial contexts. There are several algebraic and combinatorial relationships between them. Here, we state and prove four new identities concerning the determinants of matrices whose entries are unsigned Stirling numbers of first kind and Stirling numbers of second kind. We also observe an interrelationship between them based on our identities.
We generalize a construction by Treash of a Steiner triple system on \(2v+1\) points that embeds a Steiner triple system on \(v\) points. We show that any Steiner quadruple system on \(v+1\) points may be embedded in a Steiner quadruple system on \(2v+2\) points.
A \((\lambda K_n, G)\)-design is a partition of the edges of \(\lambda K_n\), into sub-graphs each of which is isomorphic to \(G\). In this paper, we investigate the existence of \((K_n, G_{16})\)-design and \((K_n, G_{20})\)-design, and prove that the necessary conditions for the existence of the two classes of graph designs are also sufficient.
Every labeling of the vertices of a graph with distinct natural numbers induces a natural labeling of its edges: the label of an edge \(ae\) is the absolute value of the difference of the labels of \(a\) and \(e\). A labeling of the vertices of a graph of order \(p\) is minimally \(k\)-equitable if the vertices are labeled with elements of \({1,2, \ldots, p}\) and in the induced labeling of its edges, every label either occurs exactly \(k\) times or does not occur at all. We prove that the corona graph \(C_{2n}OK_1\) is minimally \(4\)-equitable.
A set of Bishops cover a board if they attack all unoccupied squares. What is the minimum number of Bishops needed to cover an \(k \times n\) board \(?\) Yaglom and Yaglom showed that if \(k = n\), the answer is \(n\). We extend this result by showing that the minimum is \(2\lfloor \frac{n}{2}\rfloor\) if \(k 2k > 2\), a cover is given with \(2\lfloor\frac{k+n}{2}\rfloor\) Bishops. We conjecture that this is the minimum value. This conjecture is verified when \(k \leq 3\) or \(n \leq 2k + 5\).
It is proved that the following graphs are harmonious:(1) shell graphs (2) cycles with the maximum possible number of concurrent alternate chords (3) Some families of multiple shells
In this paper, we determine all harmonious graphs of order \(6\).
All graphs in this paper are finite, simple and undirected. We shall use the basic notation and terminology of graph theory as in [1].
Let \(R(n)\) denote the number of two-color partitions of \(n\). We obtain several identities concerning \(R(n)\).
We show that if \(M(n, m)\) denotes the time of a \((u, v)\)-minimum cut computation in a directed graph with \(n \geq 2\) nodes, \(m\) edges, and \(s\) and \(t\) are two distinct given nodes, then there exists an algorithm with \(O(n^2m+n\cdot M(n, m))\) running time for the directed minimum odd (or even) \((s, t)\)-cut problem and for its certain generalizations.
Basic properties of in-degree distribution of a general model of random digraphs \(D(n, \mathcal{P})\) are presented. Then some relations between random digraphs \(D(n, \mathcal{P})\) for different probability distributions \(\mathcal{P}\)’s are studied. In this context, a problem of the existence of a threshold function for every monotone digraph property of \(D(n, \mathcal{P})\) is discussed.
For a given structure (graph, multigraph, or pseudograph) \(G\) and an integer \(r \geq \Delta(G)\), a smallest inducing \(r\)-regularization of \(G\) (which is an \(r\)-regular superstructure of the smallest possible order, with bounded edge multiplicities, and containing \(G\) as an induced substructure) is constructed.
It is an established fact that some graph-theoretic extremal questions play an important part in the investigation of communication network vulnerability. Questions concerning the realizability of graph invariants are generalizations of these extremal problems. We define a \((p, q, \lambda, \delta)\) graph as a graph having \(p\) points, \(q\) lines, line connectivity \(\lambda\) and minimum degree \(\delta\). An arbitrary quadruple of integers \((a, b, c, d)\) is called \((p, q, \lambda, \delta)\) realizable if there is a \((p, q, \lambda, \delta)\) graph with \(p = a, q = b, \lambda = c\), and \(\delta = d\). Inequalities representing necessary and sufficient conditions for a quadruple to be \((p, q, \lambda, \delta)\) realizable are derived. In recent papers, the author gave necessary and sufficient conditions for \((p, q, \kappa, \Delta), (p, q, \lambda, \Delta), (p, q, \delta, \Delta)\) and \((p, q, \kappa, \delta)\) realizability, where \(\Delta\) denotes the maximum degree for all points in a graph and \(\lambda\) denotes the point connectivity of a graph. Boesch and Suffel gave the solutions for \((p, q, \kappa), (p, q, \lambda), (p, q, \delta), (p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability in earlier manuscripts.
An aperiodic perfect map (APM) is an array with the property that each possible array of certain size, called a window, arises exactly once as a subarray in the array. In this article, we give some constructions which imply a complete answer for the existence of APMs with \(2 \times 2\) windows for any alphabet size.
A \(4\)-regular graph \(G\) is called a \(4\)-circulant if its adjacency matrix \(A(G)\) is a circulant matrix. Because of the special structure of the eigenvalues of \(A(G)\), the rank of such graphs is completely determined. We show how all disconnected \(4\)-circulants are made up of connected \(4\)-circulants and classify all connected \(4\)-circulants as isomorphic to one of two basic types.
Let \([n, k, d; g]\)-codes be linear codes of length \(n\), dimension \(k\) and minimum Hamming distance \(d\) over \(\mathrm{GF}(g)\). Let \(d_8(n, k)\) be the maximum possible minimum Hamming distance of a linear \([n, k, d; 8]\)-code for given values of \(n\) and \(k\). In this paper, twenty-two new linear codes over \(\mathrm{GF}(8)\) are constructed which improve the bounds on \(d_8(n, k)\).
We find new full orthogonal designs in order \(56\) and show that of
\(1285\) possible \(OD(56; s_1, s_2, s_3,56 – s_1 – s_2 – s_3)\) \(163\) are known, of
\(261\) possible \(OD(56; s_1, s_2, 56 – s_1 – s_2)\) \(179\) are known. All possible
\(OD(56; s_1,56 – s_1)\) are known.
Sattolo has presented an algorithm to generate cyclic permutations at random. In this note, the two parameters “number of moves” and “distance” are analyzed.
In this paper, we shall classify the self-complementary graphs with minimum degree exactly \(2\).
A graphical partition of the even integer \(n\) is a partition of \(n\) where each part of the partition is the degree of a vertex in a simple graph and the degree sum of the graph is \(n\). In this note, we consider the problem of enumerating a subset of these partitions, known as graphical forest partitions, graphical partitions whose parts are the degrees of the vertices of forests (disjoint unions of trees). We shall prove that
\[gf(2k) = p(0) + p(1) + p(2) + \cdots + p(k-1)\]
where \(g_f(2k)\) is the number of graphical forest partitions of \(2k\) and \(p(j)\) is the ordinary partition function which counts the number of integer partitions of \(j\).
We make further progress towards the forbidden-induced-subgraph characterization of the graphs with Hall number \(\leq 2\). We solve several problems posed in [4] and, in the process, describe all “partial wheel” graphs with Hall number \(\geq 2\) with every proper induced subgraph having Hall number \(\leq 2\).
A radio labeling of a connected graph $G$ is an assignment of distinct, positive integers to the vertices of \(G\), with \(x \in V(G)\) labeled \(c(x)\), such that
\[d(u, v) + |c(u) – c(v)| \geq 1 + diam(G)\]
for every two distinct vertices \(u,v\) of \(G\), where \(diam(G)\) is the diameter of \(G\). The radio number \(rn(c)\) of a radio labeling \(c\) of \(G\) is the maximum label assigned to a vertex of \(G\). The radio number \(rn(G)\) of \(G\) is \(\min\{rn(c)\}\) over all radio labelings \(c\) of \(G\). Radio numbers of cycles are discussed and upper and lower bounds are presented.
Dudeney’s round table problem was proposed about one hundred years ago. It is already solved when the number of people is even, but it is still unsettled except for only a few cases when the number of people is odd.
In this paper, a solution of Dudeney’s round table problem is given when \(n = p+2\), where \(p\) is an odd prime number such that \(2\) is the square of a primitive root of \(\mathrm{GF}(p)\), \(p \equiv 1 \pmod{4}\), and \(3\) is not a quadratic residue modulo \(p\).
Let \(r(a)\) be the replication number of the vertex \(a\) of a path design \(P(v,k, 1)\), \(k \geq 3\). Let \(\bar{r}(v,k) = \text{min}\{\text{max}_{a\in V} \,r(a) | (V,\mathcal{B}) \text{ is a } P(v,k, 1)\}\). A path design \(P(v,k,1)\), \((W,\mathcal{D})\), is said to be \({almost\; balanced}\) if \(\bar{r}(v,k) – 1 \leq r(y) \leq \bar{r}(v,k)\) for each \(y \in W\). Let \(v \equiv 0 \text{ or } 1 \pmod{2(k-1)}\) (for each odd \(k\), \(k \geq 3\)) and let \(v_y \equiv 0 \text{ or } 1 \pmod{k-1}\) (for each even \(k\), \(k \geq 4\)). In this note, we determine the spectrum \(\mathcal{B}\mathcal{S}\mathcal{A}\mathcal{B}\mathcal{P}(v,k,1)\) of integers \(x\) such that there exists an almost balanced path design \(P(v,k, 1)\) with a blocking set of cardinality \(x\).
A border of a string \(x\) is a proper (but possibly empty) prefix of \(x\) that is also a suffix of \(x\). The \({border \;array}\) \(\beta = \beta[1..n]\) of a string \(x = x[1..n]\) is an array of nonnegative integers in which each element \(\beta(i)\), \(1 \leq i \leq n\), is the length of the longest border of \(x[1..i]\). In this paper, we first present a simple linear-time algorithm to determine whether or not a given array \(y = y[1..n]\) of integers is a border array of some string on an alphabet of unbounded size, and then a slightly more complex linear-time algorithm for an alphabet of any given (bounded) size \(\alpha\). We then consider the problem of generating all possible distinct border arrays of given length \(n\) on a bounded or unbounded alphabet, and doing so in time proportional to the number of arrays generated. A previously published algorithm that claims to solve this problem in constant time per array generated is shown to be incorrect, and new algorithms are proposed. We conclude with an equally efficient on-line algorithm for this problem.
In developing an observation made by the author concerning a class of expansions of the sine function, M. Xinrong has recently analysed the question of a generalised form through a succinct use of linear operator theory. This paper constitutes an extension of his work, in which the current problem is solved completely by examining the generating function of a finite sequence central to the formulation.
For graphs \(G\) and \(H\), the Ramsey number \(R(G, H)\) is the least integer \(n\) such that every 2-coloring of the edges of \(K_n\) contains a subgraph isomorphic to \(G\) in the first color or a subgraph isomorphic to \(H\) in the second color. Graph \(G\) is a \((C_4, K_n)\)-graph if \(G\) doesn’t contain a cycle \(C_4\) and \(G\) has no independent set of order \(n\). Jayawardene and Rousseau showed that \(21 \leq R(C_4, K_7) \leq 22\). In this work, we determine \(R(C_4, K_7) = 22\) and \(R(C_4, K_8) = 26\), and enumerate various families of \((C_4, K_n)\)-graphs. In particular, we construct all \((C_4, K_n)\)-graphs for \(n < 7\), and all \((C_4, K_n)\)-graphs on at least 19 vertices. Most of the results are based on computer algorithms.
For \(\text{k}>0\), we call a graph G=(V,E) as \(\underline{\text{Z}_\text{k}-magic}\) if there exists an edge labeling \(\text{I: E(G)} \rightarrow \text{Z}_\text{k}^*\) such that the induced vertex set labeling \(\text{I}^+: \text{V(G)} \rightarrow \text{Z}_\text{k}\) defined by
\[\text{I}^+(\text{v}) = \Sigma \{(\text{I(u,v)) : (u,v)} \in \text{E(G)}\}\]
is a constant map. We denote the set of all \(k\) such that \(G\) is \(k\)-magic by \(IM(G)\). We call this set as the \(\textbf{integer-magic spectrum}\) of \(G\). This paper deals with determining the integer-magic spectra of powers of paths \(\text{P}\text{n}^\text{k}\) for \(k=2\) and \(3\). We also show that IM(\(\text{P}_{2\text{k}}^\text{k}) = \text{N}\setminus\{2\}\) for all odd integers \(\text{k}>1\). Finally, a conjecture for \(IM\)\((\text{P}_\text{n}^\text{k})\) for \(\text{k}\geq4\) is proposed.
A new graph labeling problem on simple graphs called edge-balanced labeling is introduced by Kong and Lee [11]. They conjectured that all trees except \(K_{1,n}\) where \(n\) is odd, and all connected regular graphs except \(K_2\) are edge-balanced. In this paper, we extend the concept of edge-balanced labeling to multigraphs and completely characterize the edge-balanced multigraphs. Thus, we proved that the above two conjectures are true. A byproduct of this result is a proof that the problem of deciding whether a graph is edge-balanced does not belong to NP-hard.
Let \(\Gamma\) be a finite group and let \(X\) be a subset of \(\Gamma\) such that \(X^{-1} = X\) and \(1 \notin X\). The conjugacy graph \(\text{Con}(\Gamma; X)\) has vertex set \(\Gamma\) and two vertices \(g, h \in \Gamma\) are adjacent in \(\text{Con}(\Gamma; X)\) if and only if there exists \(x \in X\) with \(g = xhx^{-1}\). The components of a conjugacy graph partition the vertices into conjugacy classes (with respect to \(X\)) of the group. Sufficient conditions for a conjugacy graph to have either vertex-transitive or arc-transitive components are provided. It is also shown that every Cayley graph is the component of some conjugacy graph.
By definition, the vertices of a de Bruijn graph are all strings of length \(n-1\) (\(n>1\)) over a fixed finite alphabet. The edges are all strings of length \(n\) over the same alphabet. The directed edge \(a_1\ldots a_n\) joins vertex \(a_1\ldots a_{n-1}\) to vertex \(a_2\ldots a_n\). A block code over an alphabet of \(\sigma\) elements is comma-free if it does not contain any overlap of codewords. Representing the codewords of comma-free codes as directed edges of the de Bruijn graph, we give sufficient conditions that a bipartite subgraph of the de Bruijn graph whose underlying undirected graph is connected is a comma-free code.
Given two graphs \(G\) and \(H\), the composition of \(G\) with \(H\) is the graph with vertex set \(V(G) \times V(H)\) in which \((u_1, v_1)\) is adjacent to \((u_2, v_2)\) if and only if \(u_1u_2 \in E(G)\) or \(u_1 = u_2\) and \(v_1v_2 \in E(H)\). In this paper, we prove that the composition of a regular supermagic graph with a null graph is supermagic. With the help of this result, we show that the composition of a cycle with a null graph is always supermagic.
In this paper, we discuss a self-adjusting and self-improving combinatorial optimization algorithm. Variations of this algorithm have been successfully applied in recent research in Design Theory. The approach is simple but general and can be applied in any instance of a combinatorial optimization problem.
Let \(n, x\) be positive integers satisfying \(1 < x < n\). Let \(H_{n,x}\) be a group admitting a presentation of the form \(\langle a, b \mid a^n = b^2 = (ba)^x = 1 \rangle\). When \(x = 2\) the group \(H_{n,x}\) is the familiar dihedral group, \(D_{2n}\). Groups of the form \(H_{n,x}\) will be referred to as generalized dihedral groups. It is possible to associate a cubic Cayley graph to each such group, and we consider the problem of finding the isoperimetric number, \(i(G)\), of these graphs. In section two we prove some propositions about isoperimetric numbers of regular graphs. In section three the special cases when \(x = 2, 3\) are analyzed. The former case is solved completely. An upper bound, based on an analysis of the cycle structure of the graph, is given in the latter case. Generalizations of these results are provided in section four. The indices of these graphs are calculated in section five, and a lower bound on \(i(G)\) is obtained as a result. We conclude with several conjectures suggested by the results from earlier sections.
Let \(G\) be a transitive permutation group on a set \(Q\). The orbit decompositions of the actions of \(G\) on the sets of ordered \(n\)-tuples with elements repeated at most three times are studied. The decompositions involve Stirling numbers and a new class of related numbers, the so-called tri-restricted numbers. The paper presents exponential generating functions for the numbers of orbits, and examines relationships between various powers of the \(G\)-set involving Stirling numbers, the tri-restricted numbers, and the coefficients of Bessel polynomials.
Let \(\Gamma\) be a finite group and let \(\Delta\) be a generating set for \(\Gamma\). A Cayley map associated with \(\Gamma\) and \(\Delta\) is an oriented 2-cell embedding of the Cayley graph \(G_\Delta(\Gamma)\) such that the rotation of arcs emanating from each vertex is determined by a unique cyclic permutation of generators and their inverses. A formula for the average Cayley genus is known for the dihedral group with generating set consisting of all the reflections. However, the known formula involves sums of certain coefficients of a generating function and its format does not specifically indicate the Cayley genus distribution. We determine a simplified formula for this average Cayley genus as well as provide improved understanding of the Cayley genus distribution.
A \((p,q)\) graph \(G\) is \({total\; edge-magic}\) if there exists a bijection \(\text{f}: \text{V} \cup \text{E} \rightarrow \{1,2, \ldots, \text{p+q}\}\) such that \(\forall\, \text{e} = \text{(u,v)} \in \text{E}\), f(u) + f(e) + f(v) = constant. A total edge-magic graph is a \({super \;edge-magic\; graph}\) if \(\text{f(V(G))} = \{1,2, \ldots, \text{p}\}\). For \(\text{n} \geq 2\), let \(\text{a}_1, \text{a}_2, \text{a}_3, \ldots, \text{a}_\text{n}\) be a sequence of increasing non-negative integers. A n-star \(S(\text{a}_1, \text{a}_2, \text{a}_3, \ldots, \text{a}_\text{n})\) is a disjoint union of n stars \(\text{St}(\text{a}_1),\text{ St}(\text{a}_2), \ldots, \text{St}(\text{a}_\text{n})\). In this paper, we investigate several classes of n-stars that are super edge-magic.
For \(k>0\), we call a graph \(G=(V,E)\) as \(\underline{Z_k-magic}\) if there exists a labeling \(I: E(G) \rightarrow {Z}_k^*\) such that the induced vertex set labeling \(I^+: V(G) \rightarrow {Z}_k\)
\[I^+(v) = \Sigma \{I(u,v) : (u,v) \in E(G)\}\]
is a constant map. We denote the set of all \(k\) such that \(G\) is \(k\)-magic by \(IM(G)\). We call this set as the integer-magic spectrum of \(G\). We investigate these sets for general graphs.
Several \(q\)-polynomial identities are derived from a consideration of classical finite polar spaces. One class of identities is obtained by sorting maximal singular spaces with respect to a given one. Another class is derived from sorting sesquilinear and quadratic forms according to their radicals.
We describe a concrete data structure, called a sequence-tree, that represents sequences of arbitrary elements, along with associated algorithms that allow single element access and assignment, subsequence extraction (slicing), and concatenation to be done in logarithmic time relative to sequence length. These operations are functional, in the sense that they leave their operand sequences unchanged. For a single sequence, space is linear in the sequence length. Where a set of multiple sequences have been computed by these algorithms, space may be sublinear, because of node sharing. Sequence-trees use immutable, shared, dynamically allocated nodes and thus may require garbage collection, if some of the sequences in a set are abandoned. However, the interconnection of nodes is non-cyclic, so explicitly programmed collection using reference counting is reasonable, should a general-purpose garbage collector be unavailable. Other sequence representations admit only to linear-time algorithms for one or more of the aforementioned operations. Thus sequence-trees give improved performance in applications where all the operations are needed.
This paper is an expository treatment of the Leftover Hash Lemma and some of its applications in cryptography and complexity theory.
In this paper, we characterize the potentially \(C_k\)-graphic sequence for \(k = 3, 4, 5\). These characterizations imply several theorems due to P. Erdős, M. S. Jacobson, and J. Lehel [1], R. J. Gould, M. S. Jacobson, and J. Lehel [2], and C. H. Lai [5] and [6], respectively.
Bailey, Cheng, and Kipnis [3] developed a method for constructing trend-free run orders of factorial experiments called the generalized fold-over method (GFM). In this paper, we use the GFM of constructing run orders of factorial experiments to give a systematic method of constructing magic squares of higher order.
In this paper, we focus on the identification of Latin interchanges in Latin squares that are the direct product of Latin squares of smaller orders. The results we obtain on Latin interchanges will be used to identify critical sets in direct products. This work is an extension of research carried out by Stinson and van Rees in \(1982\).
A \((g,k; \lambda)\)-difference matrix over the group \((G, o)\) of order \(g\) is a \(k\) by \(g\lambda\) matrix \(D = (d_{ij})\) with entries from \(G\) such that for each \(1 \leq i < j \leq k\), the multiset \(\{d_{il}\) o \(d_{jl}^{-1} \mid 1 \leq l \leq g\lambda\}\) contains every element of \(G\) exactly \(\lambda\) times. Some known results on the non-existence of generalized Hadamard matrices, i.e., \((g,g\lambda; \lambda)\)-difference matrices, are extended to \((g, g-1; \lambda)\)-difference matrices.
The notion of convexity in graphs is based on the one in topology: a set of vertices \(S\) is convex if an interval is entirely contained in \(S\) when its endpoints belong to \(S\). The order of the largest proper convex subset of a graph \(G\) is called the convexity number of the graph and is denoted \(con(G)\). A graph containing a convex subset of one order need not contain convex subsets of all smaller orders. If \(G\) has convex subsets of order \(m\) for all \(1 \leq m \leq con(G)\), then \(G\) is called polyconvex. In response to a question of Chartrand and Zhang [3], we show that, given any pair of integers \(n\) and \(k\) with \(2 \leq k < n\), there is a connected triangle-free polyconvex graph \(G\) of order \(n\) with convexity number \(k\).
In this work, \(\Gamma\) denotes a finite, simple, and connected graph. The \(k\)-excess \(e_k(H)\) of a set \(H \subseteq V(\Gamma)\) is defined as the cardinality of the set of vertices that are at distance greater than \(k\) from \(H\), and the \(k\)-excess \(e_k(h)\) of all \(A\)-subsets of vertices is defined as
\[e_k(h) = \max_{H \subset V(\Gamma),|H|=h} \{ e_k(H) \}\]
The \(k\)-excess \(e_k\) of the graph is obtained from \(e_k(h)\) when \(h = 1\). Here we obtain upper bounds for \(e_k(h)\) and \(e_k\) in terms of the Laplacian eigenvalues of \(\Gamma\).
Let \(G\) be a \(k\)-connected graph and let \(F\) be the simple graph obtained from \(G\) by removing the edge \(xy\) and identifying \(x\) and \(y\) in such a way that the resulting vertex is incident to all those edges (other than \(xy\)) which are originally incident to \(x\) or \(y\). We say that \(e\) is contractible if \(F\) is \(k\)-connected. A bowtie is the graph consisting of two triangles with exactly one vertex in common. We prove that if a \(k\)-connected graph \(G\) (\(k \geq 4\)) has no contractible edge, then there exists a bowtie in \(G\).
We prove that the number of nonisomorphic minimal \(2\)-colorings of the edges of \(K_{4n+3}\) is at least \(2n\) less than the number of nonisomorphic minimal \(2\)-colorings of the edges of \(K_{4n+2}\), where \(n\) is a nonnegative integer. Harary explicitly gave all the nonisomorphic minimal \(2\)-colorings of the edges of \(K_6\). In this paper, we give all the nonisomorphic minimal \(2\)-colorings of the edges of \(K_7\).
We restate a recent improvement of the inclusion-exclusion principle in terms of valuations on distributive lattices and present a completely new proof of the result. Moreover, we establish set-theoretic identities and logical equivalences of inclusion-exclusion type, which have not been considered before.
Let \(\delta(G)\) denote the minimum degree of a graph \(G\). We prove that for \(t \geq 4\) and \(k \geq 2\), a graph \(G\) of order at least \((t + 1)k + 2t^2 – 4t + 2\) with \(\delta(G) \geq k+t- 1\) contains \(k\) pairwise vertex-disjoint \(K_{1,t}\)’s.
In this paper, we construct a squag \(SQG(3n)\) of cardinality \(3n\) that contains three given arbitrary squags \(SQG(n)\)s as disjoint subquags. Accordingly, we can construct a subdirectly irreducible squag \(SQG(3n)\), for each \(n \geq 7\), with \(n \equiv 0, 3 \pmod{6}\). Also, we want to review the shape of the congruence lattice of non-simple squags \(SQG(n)\) for some \(n\) and to give a classification of the class of all \(SQG(21)\)s and the class of all \(SQG(27)\)s according to the shape of its congruence lattice. \(SQG(21)\)s are classified into three classes and \(SQG(27)\)s are classified into four classes. The construction of \(SQG(3n)\), which is given in this paper, helps us to construct examples of each class of both \(SQG(21)\)s and \(SQG(27)\)s.
We show how to produce algebraically a complete orthogonal set of Latin squares from a left quasifield and how to generate algebraically a maximal set of self-orthogonal Latin squares from a left nearfield.
A \((k;g)\)-graph is a \(k\)-regular graph with girth \(g\). A \((k; g)\)-cage is a \((k; g)\)-graph with the least possible number of vertices. In this paper, we prove that all \((4; g)\)-cages are \(4\)-connected, a special case of the conjecture about \((k; g)\)-cages’ connectivity made by H.L. Fu \(et\; al [1]\).
A set \(S\) of vertices of a graph \(G\) is a total dominating set if every vertex of \(V(G)\) is adjacent to some vertex in \(S\). The total domination number \(\gamma_t(G)\) is the minimum cardinality of a total dominating set of \(G\). Let \(G\) be a spanning subgraph of \(K_{s,s}\), and let \(H\) be the complement of \(G\) relative to \(K_{s,s}\); that is, \(K_{s,s} = G \oplus H\) is a factorization of \(K_{s,s}\). The graph \(G\) is \(k\)-critical relative to \(K_{s,s}\) if \(\gamma_t(G) = k\) and \(\gamma_t(G + e) < k\) for all \(e \in E(H)\). We study \(k_t\)-critical graphs relative to \(K_{s,s}\) for small values of \(k\). In particular, we characterize the \(3\)-critical and \(4_t\)-critical graphs.
Let \(S\) be a nonempty subset of the cyclic group \(\mathbb{Z}_p\), where \(p\) is an odd prime. Denote the \(n\)-fold sum of \(S\) as \(n..S\). That is,\(n..S = \{s_1 + \cdots + s_n \mid s_1, \ldots, s_n \in S\}.\) We say that \(S\) is an \((n, 0)\)-set if \(0 \notin n..S\). Let \(k, s\) be integers with \(k \geq 2\) such that \(p-1 = ks\). In this paper, we determine the number of \((k, 0)\)-sets of \(\mathbb{Z}_p\) which are in arithmetic progression and show explicitly the forms taken by those \((k, 0)\)-sets which achieve the maximum cardinality.
In this paper, necessary and sufficient conditions are given for the existence of extended \(5\)-cycle systems of order \(n\) which have \(r\) idempotent elements.
An \((f,2)\)-graph is a multigraph \(G\) such that each vertex of \(G\) has degree either \(f\) or \(2\). Let \(S(n, f)\) denote the simple graph whose vertex set is the set of unlabeled \((f,2)\)-graphs of order no greater than \(n\) and such that \(\{G, H\}\) is an edge in \(S(n, f)\) if and only if \(H\) can be obtained from \(G\) by either an insertion or a suppression of a vertex of degree \(2\). We also consider digraphs whose nodes are labeled or unlabeled \((f, 2)\)-multigraphs and with arcs \((G, H)\) defined as for \(\{G, H\}\).
We study the structure of these graphs and digraphs. In particular, the diameter of a given component is determined. We conclude by defining a random process on these digraphs and derive some properties. Chemistry applications are suggested.
Given a coloring \(f\) of Euclidean space \(\mathbb{R}^n\) and some group \(G\) of its transformations, its subsets \(A\) and \(B\) are said to be colored similarly, if there exists \(g \in G\), such that \(B = g(A)\) and \(f(a) = f(g(a))\), for all \(a \in A\). From our earlier result [12] it follows that there are \(2\)-colorings of \(\mathbb{R}^n\), in which no two different line segments are colored similarly with respect to isometries. The main purpose of this paper is to investigate other types of such pattern avoiding colorings. In particular, we consider topological as well as measure theoretic aspects of the above scene. Our motivation for studying this topic is twofold. One is that it extends square-free colorings of \(\mathbb{R}\), introduced in [2] as a continuous version of the famous non-repetitive sequences of Thue. The other is its relationship to some exciting problems and results of Euclidean Ramsey Theory, especially those concerning avoiding distances.
In this paper, a definition of perfect binary matroids is considered and it is shown that, analogous to the Perfect Graph Theorem of Lovász and Fulkerson, the complement of a perfect matroid is also a perfect matroid. In addition, the classes of critically imperfect graphic matroids and critically imperfect graphs are compared.
A \((p,q)\) graph \(G\) is edge-magic if there exists a bijective function \(f : V(G) \cup E(G) \to \{1,2,\ldots,p+q\}\) such that \(f(u) + f(v) + f(uv) = k\) is a constant, called the valence of \(f\), for any edge \(uv\) of \(G\). Moreover, \(G\) is said to be super edge-magic if \(f(V(G)) = \{1,2,\ldots,p\}\). Every super edge-magic \((p,q)\) graph is cordial, and it is harmonious and sequential whenever it is a tree or \(q \geq p\). In this paper, it is shown to be edge-antimagic as well. The super edge-magic properties of several classes of connected and disconnected graphs are studied. Furthermore, we prove that there can be arbitrarily large gaps among the possible valences for certain super edge-magic graphs. We also establish that the disjoint union of multiple copies of a super edge-magic linear forest is super edge-magic if the number of copies is odd.
In this paper, necessary and sufficient conditions are given for the metamorphosis of a \(\lambda\)-fold \(K_{3,3}\)-design of order \(n\) into a \(\lambda\)-fold \(6\)-cycle system of order \(n\), by retaining one \(6\)-cycle subgraph from each copy of \(K_{3,3}\), and then rearranging the set of all the remaining edges, three from each \(K_{3,3}\), into further \(6\)-cycles so that the result is a \(\lambda\)-fold \(6\)-cycle system.
Partially balanced diallel cross block designs with \(m\) associate classes are defined and two general methods of construction are presented. Two-associate class designs based upon group divisible, triangular, and extended group divisible association schemes obtained using the general methods are also given. Tables of designs for no more than \(24\) parental lines are provided.
Given a non-planar graph \(G\) with a subdivision of \(K_5\) as a subgraph, we can either transform the \(K_5\)-subdivision into a \(K_{3,3}\)-subdivision if it is possible, or else we obtain a partition of the vertices of \(G\backslash K_5\) into equivalence classes. As a result, we can reduce a projective planarity or toroidality algorithm to a small constant number of simple planarity checks [6] or to a \(K_{3,3}\)-subdivision in the graph \(G\). It significantly simplifies algorithms presented in [7], [10], and [12]. We then need to consider only the embeddings on the given surface of a \(K_{3,3}\)-subdivision, which are much less numerous than those of \(K_5\).
Let \(M(d,n)\) denote the minimax number of group tests required for the identification of the \(d\) defectives in a set of \(n\) items. It was conjectured by Hu, Hwang, and Wang that \(M(d,n) = n-1\) for \(n \leq 3d\), a surprisingly difficult combinatorial problem with very little known. The best known result is \(M(d,n) = n-1\) for \(n \leq \frac{42}{16}d\) by Du and Hwang. In this note, we improve their result by proving \(M(d,n) = n – 1\) for \(d \geq 193\) and \(n \leq \frac{42}{16}d\).
In this paper, we investigate the divisibility of \(mn\) by \(am+bn+c\) for given \(a\), \(b\), and \(c\). We give the necessary and sufficient condition for the divisibility, that is, \(am + bn + c\) divides \(mn\). We then present the structure of the set of pairs \([m,n]\) that satisfies the divisibility. This structure is represented by a directed graph and we prove the necessary and sufficient condition for the graph to have a binary tree structure. In particular, for \(c = -1\), we show double binary tree structures on the set.
We give a necessary and sufficient condition of Hall’s type for a family of sets of even cardinality to be decomposable into two subfamilies having a common system of distinct representatives. An application of this result to partitions of Steiner Triple Systems into small configurations is presented.
In this paper, we construct \(2\)-factorizations of \(K_n\) (\(n\) odd) containing a specified number, \(k\), of \(6\)-cycles, for all integers \(k\) between 0 and the maximum possible expected number of \(6\)-cycles in any \(2\)-factorization, and for all odd \(n\), with no exceptions.
We deal with \((a,d)\)-face antimagic labelings of a certain class of plane quartic graphs. A connected plane graph \(G = (V, E, F)\) is said to be \((a,d)\)-\({face\; antimagic}\) if there exist positive integers \(a\) and \(d\), and a bijection \(g : E(G) \rightarrow \{1,2,…,|E(G)|\}\) such that the induced mapping \(\varphi_g : F(G) \rightarrow {N}\), defined by \(\varphi_g(f) = \sum\{g(e): e \in E(G) \text{ adjacent to face } f\}\), is injective and \(\varphi_g(F) = \{a,a+d,…,a+ (|F(G)| – 1)d\}\).
Let \(G\) be a graph with vertex set \(V\) and edge set \(E\). A vertex labelling \(f : V \rightarrow \{0,1\}\) induces an edge labelling \(\overline{f} : E \rightarrow \{0,1\}\) defined by \(\overline{f}(uv) = |f(u) – f(v)|\). Let \(v_f(0), v_f(1)\) denote the number of vertices \(v\) with \(f(v) = 0\) and \(f(v) = 1\) respectively. Let \(e_f(0), e_f(1)\) be similarly defined. A graph is said to be cordial if there exists a vertex labeling \(f\) such that \(|v_f(0) – v_f(1)| \leq 1\) and \(|e_f(0) – e_f(1)| \leq 1\). In this paper, we show that for every positive integer \(t\) and \(n\) the following families are cordial: (1) Helms \(H_{n}\). (2) Flower graphs \(FL_{n}\). (3) Gear graphs \(G_{n}\). (4) Sunflower graphs \(SFL_{n}\). (5) Closed helms \(CH_{n}\). (6) Generalised closed helms \(CH(t,n)\). (7) Generalised webs \(W(t, n)\).
A cycle \(C\) of a graph \(G\) is called a \(q\)-dominating cycle if every vertex of \(G\) which is not contained in \(C\) is adjacent to at least \(q\) vertices of \(C\). Let \(G\) be a \(k\)-connected graph with \(k \geq 2\). We present a sufficient condition, in terms of the degree sum of \(k + 1\) independent vertices, for \(G\) to have a \(qg\)-dominating cycle. This is an extension of a 1987 result by J.A. Bondy and G. Fan. Furthermore, examples will show that the given condition is best possible.
In an earlier paper [11], we proved that there does not exist any \(\Delta\)-critical graph of even order with five major vertices. In this paper, we prove that if \(G\) is a \(\Delta\)-critical graph of odd order \(2n+1\) with five major vertices, then \(e(G) = n\Delta+1\). This extends an earlier result of Chetwynd and Hilton, and also completes our characterization of graphs with five major vertices. In [9], we shall apply this result to establish some results on class 2 graphs whose core has maximum degree two.
In this paper, uniquely list colorable graphs are studied. A graph \(G\) is said to be uniquely \(k\)-list colorable if it admits a \(k\)-list assignment from which \(G\) has a unique list coloring. The minimum \(k\) for which \(G\) is not uniquely \(k\)-list colorable is called the \(m\)-number of \(G\). We show that every triangle-free uniquely colorable graph with chromatic number \(k+1\) is uniquely \(k\)-list colorable. A bound for the \(m\)-number of graphs is given, and using this bound it is shown that every planar graph has \(m\)-number at most \(4\). Also, we introduce list criticality in graphs and characterize all \(3\)-list critical graphs. It is conjectured that every \(\chi_\ell’\)-critical graph is \(\chi’\)-critical, and the equivalence of this conjecture to the well-known list coloring conjecture is shown.
A labeling \(f\) of the vertices of a graph \(G\) is said \(k\)-\({equitable}\) if each weight induced by \(f\) on the edges of \(G\) appears exactly \(k\) times. A graph \(G\) is said \({equitable}\) if for every proper divisor \(k\) of its size, the graph \(G\) has a \(k\)-equitable labeling.
A graph \(G\) is a corona graph if \(G\) is obtained from two graphs, \(G_1\) and \(G_2\), taking one copy of \(G_ 1\), which is supposed to have order \(p\), and \(p\) copies of \(G_2\), and then joining by an edge the \(k^{th}\) vertex of \(G_1\) to every vertex in the \(k^{th}\) copy of \(G_2\). We denote \(G\) by \(G_1 \otimes G_2\).
In this paper, we proved that the corona graph \(C_n \otimes K_1\) is equitable. Moreover, we show \(k\)-equitable labelings of the corona graph \(C_m \otimes nK_1\), for some values of the parameters \(k, m,\) and \(n\).
In this paper, we derive a necessary existence condition involving the parameters of a balanced array (B-array) with two symbols and of strength \(t = 8\). Consequently, we demonstrate that the existence condition derived here can provide us with useful information on the maximum number of constraints for B-arrays with a given number of columns.
A set of \(n+1\) orthogonal squares of order \(n\) is known to be equivalent to a complete set of \(n-1\) mutually orthogonal Latin squares of order \(n\) together with canonical row and column squares. In this note, we show that this equivalence does not extend to orthogonal hypercubes of dimensions \(d > 2\) by providing examples of affine designs that can be represented by complete sets of type \(0\) orthogonal hypercubes but not by complete sets of orthogonal Latin hypercubes together with canonical hypercubes that generalize the row and column squares in the case where \(d = 2\). These examples also clarify the relationship between affine designs and orthogonal hypercubes that generalize the classical equivalence between affine planes and complete sets of MOLS.
We conclude with the statement of a number of conjectures regarding some open questions.
We prove that if \(S\) is a quasiminimal generating set of a group \(\Gamma\) and \(F\) is an oriented forest with \(|S| > 2\) arcs, then the Cayley graph \({Cay}(\Gamma, S)\) can be decomposed into \(|\Gamma|\) arc-disjoint subdigraphs, each of which is isomorphic to \(F\).
The quantity \(g_2^{(k)}(v)\) is the minimum number of blocks in a family of blocks from a \(v\)-set that covers all \(\binom{v}{2}\) pairs exactly twice, given the restriction that the longest block in the covering family has length \(k\) (there may be many blocks of length \(k\)). We give certain results for the case \(k = 4\).
A set of edges \(D\) in a graph \(G\) is a dominating set of edges if every edge not in \(D\) is adjacent to at least one edge in \(D\). The minimum cardinality of an edge dominating set of \(G\) is the edge domination number of \(G\), denoted \(D_E(G)\). A graph \(G\) is edge domination critical, or \(EDC\), if for any vertex \(v\) in \(G\) we have \(D_E(G – v) = D_E(G) – 1\). Every graph \(G\) must have an induced subgraph \(F\) such that \(F\) is \(EDC\) and \(D_E(G) = D_E(F)\). In this paper, we prove that no tree with more than 2 vertices is \(EDC\), develop a forbidden subgraph characterization for the edge domination number of a tree, and we develop a construction that conserves the \(EDC\) property.
Let \(V\) be a finite set of order \(v\). A \((v,k,\lambda)\) covering design of index \(\lambda\) and block size \(k\) is a collection of \(k\)-element subsets, called blocks, such that every \(2\)-subset of \(V\) occurs in at least \(\lambda\) blocks. The covering problem is to determine the minimum number of blocks, \(\alpha(v, k, \lambda)\), in a covering design. It is well known that \(\alpha(v, k, \lambda) \geq \left\lceil\frac{v}{k} \lceil \frac{v-1}{k-1}.\lambda \rceil \right\rceil=\phi(v, k, \lambda)\), where \(\lceil x \rceil\) is the smallest integer satisfying \(x\leq\lceil x \rceil\). In this paper, we determine the value \(\alpha(v,5,\lambda)\), with few possible exceptions, for \(\lambda = 3\), \(v \equiv 2 \pmod{4}\) and \(\lambda = 9, 10, v\geq5\), and \(\lambda \geq 11\), \(v \equiv 2 \pmod{4}\).
Let \(G = (V, E)\) be a connected undirected graph. Suppose a fire breaks out at a vertex of \(G\) and spreads to all its unprotected neighbours in each time interval. Also, one vertex can be protected in each time interval. We are interested in the number of vertices that can be “saved”, that is, which will never be burned. An algorithm is presented to find the optimal solution in the 2-dimensional grid graphs and 3-dimensional cubic graphs. We also determined the upper and lower bounds of the maximum number of vertices that can be saved on the large product graphs. The problem of containing the fire with one firefighter or more is also considered.
Let \(C\) be the underlying graph of a configuration of \(l\) blocks in a path design of order \(v\) and block size \(3\), \((V, \mathcal{B})\). We say that \((V, \mathcal{B})\) is \((l,C)\)-ordered if it is possible to order its blocks in such a way that each set of \(l\) consecutive blocks has the same underlying graph \(C\). In this paper, we completely solve the problem of the existence of a \((2,C)\)-ordered path design \(P(v, 3, 1)\) for any configuration having two blocks.
Summary. In this paper, we present some inequalities on balanced arrays \((B-arrays)\) of strength five with two symbols.
Let \({PG}(n,q)\) be the projective \(n\)-space over the Galois field \({GF}(q)\). A \(k\)-cap in \({PG}(n,q)\) is a set of \(k\) points such that no three of them are collinear. A \(k\)-cap is said to be complete if it is maximal with respect to set-theoretic inclusion. In this paper, using classical algebraic varieties, such as Segre varieties and Veronese varieties, some new infinite classes of caps are constructed.
We introduce Skolem arrays, which are two-dimensional analogues of Skolem sequences. Skolem arrays are ladders which admit a Skolem labelling in the sense of [2]. We prove that they exist exactly for those integers \(n = 0\) or \(1 \pmod{4}\). In addition, we provide an exponential lower bound for the number of distinct Skolem arrays of a given order. Computational results are presented which give an exact count of the number of Skolem arrays up to order \(16\).
The cyclicity of a graph is the largest integer \(n\) for which the graph is contractible to the cycle on \(n\) vertices. We prove that, for \(n\) greater than three, the problem of determining whether an arbitrary graph has cyclicity \(n\) is NP-hard. We conjecture that the case \(n = 3\) is decidable in polynomial time.
We provide a hierarchy, linearly ordered by inclusion, describing various complete sets of combinatorial objects starting with complete sets of mutually orthogonal Latin squares, generalizing to affine geometries and designs, frequency squares and hypercubes, and ending with \((t, m, s)\)-nets.
In this paper we introduce the edge-residual number \(\rho(G)\) of a graph \(G\). We give tight upper bounds for \(\rho(G)\) in terms of the eigenvalues of the Laplacian matrix of the line graph of \(G\). In addition, we investigate the relation between this novel parameter and the line completion number for dense graphs. We also compute the line completion number of complete bipartite graphs \(K_{m,n}\) when either \(m = n\) or both \(m\) and \(n\) are even numbers. This partially solves an open problem of Bagga, Beinecke and Varma [2].
We reintroduce the problem of finding square \(\pm 1\)-matrices, denoted \(c\text{-} {H}(n)\), of order \(n\), whose rows have non-zero inner product \(c\). We obtain some necessary conditions for the existence of \(c\text{-} {H}(n)\) and provide a characterization in terms of SBIBD parameters. Several new \(c\text{-} {H}(n)\) constructions are given and new connections to Hadamard matrices and \(D\)-optimal designs are also explored.
For an integer \(k \geq 1\), a vertex \(v\) of a graph \(G\) is \(k\)-geodominated by a pair \(z, y\) of vertices in \(G\) if \(d(x, y) = k\) and \(v\) lies on an \(x-y\) geodesic of \(G\). A set \(S\) of vertices of \(G\) is a \(k\)-geodominating set if each vertex \(v\) in \(V – S\) is \(k\)-geodominated by some pair of distinct vertices of \(S\). The minimum cardinality of a \(k\)-geodominating set of \(G\) is its \(k\)-geodomination number \(g_k(G)\).
A vertex \(v\) is openly \(k\)-geodominated by a pair \(x, y\) of distinct vertices in \(G\) if \(v\) is \(k\)-geodominated by \(x\) and \(y\) and \(v \neq x, y\). A vertex \(v\) in \(G\) is a \(k\)-extreme vertex if \(v\) is not openly \(k\)-geodominated by any pair of vertices in \(G\). A set \(S\) of vertices of \(G\) is an open \(k\)-geodominating set of \(G\) if for each vertex \(v\) of \(G\), either (1) \(v\) is \(k\)-extreme and \(v \in S\) or (2) \(v\) is openly \(k\)-geodominated by some pair of distinct vertices of \(S\). The minimum cardinality of an open \(k\)-geodominating set in \(G\) is its open \(k\)-geodomination number \(og_k(G)\).
It is shown that each triple \(a, b, k\) of integers with \(2 \leq a \leq b\) and \(k \geq 2\) is realizable as the geodomination number and \(k\)-geodomination number of some tree. For each integer \(k \geq 1\), we show that a pair \((a, n)\) of integers is realizable as the \(k\)-geodomination number (open \(k\)-geodomination number) and order of some nontrivial connected graph if and only if \(2 \leq a = n\) or \(2 \leq a \leq n – k + 1\).
We investigate how \(k\)-geodomination numbers are affected by adding a vertex. We show that if \(G\) is a nontrivial connected graph of diameter \(d\) with exactly \(l\) \(k\)-extreme vertices, then \(\{2, l\} \leq g_k(G) \leq og_k(G) \leq {3}g_k(G) – 2l\) for every integer \(k\) with \(2 \leq k \leq d\).
In \(1973\), Deuber published his famous proof of Rado’s conjecture regarding partition regular sets. In his proof, he invented structures called \((m, p, c)\)-sets and gave a partition theorem for them based on repeated applications of van der Waerden’s theorem on arithmetic progressions. In this paper, we give the complete proof of Deuber’s, however with the more recent parameter set proof of his partition result for \((m, p, c)\)-sets. We then adapt this parameter set proof to show that for any \(k, m, p, c\), every \(K_k\)-free graph on the positive integers contains an \((m, p, c)\)-set, each of whose rows are independent sets.
We study the weight distributions of the ternary codes of finite projective planes of order \(9\). The focus of this paper is on codewords of small Hamming weight. We show that there are many weights for which there are no codewords.
For a given sequence of nonincreasing numbers, \(\mathbf{d} = (d_1, \ldots, d_n)\), a necessary and sufficient condition is presented to characterize \(d\) when its realization is a unique labelled simple graph. If \(G\) is a graph, we consider the subgraph \(G’\) of \(G\) with maximum edges which is uniquely determined with respect to its degree sequence. We call the set of \(E(G) \setminus E(G’)\) the smallest edge defining set of \(G\). This definition coincides with the similar one in design theory.
A graph \(G\) without isolated vertices is said to be set-magic if its edges can be assigned distinct subsets of a set \(X\) such that for every vertex \(v\) of \(G\), the union of the subsets assigned to the edges incident with \(v\) is \(X\); such a set-assignment is called a set-magic labeling of \(G\). In this note, we study infinite set-magic graphs and characterize infinite graphs \(G\) having set-magic labelings \(f\) such that \(|f(e)| = 2\) for all \(e \in E(G)\).
A perfect \(\langle k,r \rangle\)-latin square \(A = (a_{i,j})\) of order \(n\) with \(m\) elements is an \(n \times n\) array in which each element occurs in each row and column, and the element \(a_{i,j}\) occurs either \(k\) times in row \(i\) and \(r\) times in column \(j\), or occurs \(r\) times in row \(i\) and \(k\) times in column \(j\). In 1989, Cai, Kruskal, Liu, and Shen studied the existence of perfect \(\langle k,r \rangle\)-latin squares. Here, a simpler construction of perfect \(\langle k,r \rangle\)-latin squares is given.
De Bruijn sequences had been well investigated in \(70s-80s\). In the past, most of the approaches used to generate de Bruijn sequences were based upon either finite field theory or combinatorial theory. This paper describes a simple approach for generating de Bruijn sequences as “seeds”, and then based upon the “seeds”, a simple procedure is presented to reproduce a class of de Bruijn sequences. Numerical results of the distribution of reproduced sequences are provided. Additionally, this paper also reports some recent applications of de Bruijn sequences in psychology and engineering.
A graph \(G(V, E)\) is a mod sum graph if there is a labeling of the vertices with distinct positive integers so that an edge is present if and only if the sum of the labels of the vertices incident on the edge, modulo some positive integer, is the label of a vertex of the graph. It is known that wheels are not mod sum graphs. The mod sum number of a graph is the minimum number of isolates that, together with the given graph, form a mod sum graph. The mod sum number is known for just a few classes of graphs. In this paper we show that the mod sum number of the \(n\)-spoked wheel, \(\rho(W_n)\), \(n \geq 5\), is \(n\) when \(n\) is odd and \(2\) when \(n\) is even.
Kahn (see [3]) reported that N. Alon, M. Saks, and P. D. Seymour made the following conjecture. If the edge set of a graph \(G\) is the disjoint union of the edge sets of \(m\) complete bipartite graphs, then \(\chi(G) \leq m+1\). The purpose of this paper is to provide a proof of this conjecture for \(m \leq 4\) and \(m \geq n – 3\) where \(G\) has \(n\) vertices.
In a graph \(G = (V, E)\), a set \(S\) of vertices (as well as the subgraph induced by \(S\)) is said to be dominating if every vertex in \(V \setminus S\) has at least one neighbor in \(S\). For a given class \(\mathcal{D}\) of connected graphs, it is an interesting problem to characterize the class \({Dom}(\mathcal{D})\) of graphs \(G\) such that each connected induced subgraph of \(G\) contains a dominating subgraph belonging to \(\mathcal{D}\). Here we determine \({Dom}(\mathcal{D})\) for \(\mathcal{D} = \{P_1, P_2, P_5\}\), \(\mathcal{D} = \{K_t \mid t \geq 1\} \cup \{P_5\}\), and \(\mathcal{D} =\) {connected graphs on at most four vertices} (where \(P_t\) and \(K_t\) denote the path and the complete graph on \(t\) vertices, respectively). The third theorem solves a problem raised by Cozzens and Kelleher [\(Discr. Math.\) 86 (1990), 101-116]. It turns out that, in each case, a concise characterization in terms of forbidden induced subgraphs can be given.
We use the results on \(5\)-GDDs to obtain optimal packings with block size five and index one. In particular, we prove that if \(v \equiv 2, 6, 10 \pmod{20}\), there exists an optimal packing with block size five on \(v\) points with at most \(32\) possible exceptions. Furthermore, if \(v \equiv 14, 18 \pmod{20}\), there exists an optimal packing with block size five on \(v\) points with a finite (large) number of possible exceptions.
A chromatic root is a root of the chromatic polynomial of some graph \(G\). E. Farrell conjectured in \(1980\) that no chromatic root can lie in the left-half plane, and in \(1991\) Read and Royle showed by direct computation that the chromatic polynomials of some graphs do have a root there. These examples, though, yield only finitely many such chromatic roots. Subsequent results by Shrock and Tsang show the existence of chromatic roots of arbitrarily large negative real part. We show that theta graphs with equal path lengths of size at least \(8\) have chromatic roots with negative real part.
The clique operator \(K\) maps a graph \(G\) into its clique graph, which is the intersection graph of the (maximal) cliques of \(G\). Recognizing clique graphs is a problem known to be in NP, but no polynomial time algorithm or proof of NP-completeness is known. In this note we prove that this recognition problem can be reduced to the case of graphs of diameter at most two.
The skewness of a graph \(G\) is the minimum number of edges that need to be deleted from \(G\) to produce a planar graph. The splitting number of a graph \(G\) is the minimum number of splitting steps needed to turn \(G\) into a planar graph; where each step replaces some of the edges \(\{u,v\}\) incident to a selected vertex \(u\) by edges \(\{u’,v\}\), where \(u’\) is a new vertex. We show that the splitting number of the toroidal grid graph \(C_n \times C_m\) is \(\min\{n,m\} – 2\delta_{n,3}\delta_{m,3} – \delta_{n,4}\delta_{m,3} – \delta_{n,3}\delta_{m,4}\) and its skewness is \(\min\{n, m\} – \delta_{n,3}\delta_{m,3 }- \delta_{n,4}\delta_{m,3} – \delta_{n,3}\delta_{m,4}\). Here, \(\delta\) is the Kronecker symbol, i.e., \(\delta_{i,j}\) is \(1\) if \(i = j\), and \(0\) if \(i \neq j\).
We introduce the notion of BP-spatial representation of a biconnected graph \(G = (V, E)\). We show that the spatiality degree of a BP-spatial representable graph is \(2(|E| – |V|)\). From this result, we derive the spatiality degree for planar and hamiltonian graphs.
We introduce the notion of premature partial Latin squares; these cannot be completed, but if any of the entries is deleted, a completion is possible. We study their spectrum, i.e., the set of integers \(t\) such that there exists a premature partial Latin square of order \(n\) with exactly \(t\) nonempty cells.
Given a digraph \(D\), its competition graph has the same vertex set and an edge between two vertices \(x\) and \(y\) if there is a vertex \(u\) so that \((x,u)\) and \((y,u)\) are arcs of \(D\). Motivated by a problem of communications, we study the competition graphs of the special digraphs known as semiorders. This leads us to define a condition on digraphs called \(C(p)\) and \(C^*(p)\) and to study the graphs arising as competition graphs of acyclic digraphs satisfying conditions \(C(p)\) or \(C^*(p)\).
A transversal cover is a set of \(gk\) points in \(k\) disjoint groups of size \(g\) and, ideally, a minimal collection of transversal subsets, called blocks, such that any pair of points not contained in the same group appears in at least one block. In this article we present a direct construction method for transversal covers using group divisible designs. We also investigate a particular infinite family of group divisible designs that yield particularly good covers.
For an ordered set \(A\) and \(B\) whose orders agree on its intersection, the gluing of \(A\) and \(B\) is defined to be the ordered set on the union of its underlying sets whose order is the transitive closure of the union of the orders of \(A\) and \(B\). The gluing number of an ordered set \(P\) is the minimum number of induced semichains (suborders of dimension at most two) of \(P\) whose consecutive gluing is \(P\). In this paper we investigate this parameter on some special ordered sets.
The aim of this paper is to give several characterizations for the following two classes of graphs: (i) graphs for which adding any \(l\) edges produces a graph which is decomposable into \(k\) spanning trees and (ii) graphs for which adding some \(l\) edges produces a graph which is decomposable into \(k\) spanning trees.
A kite is a triangle with a tail consisting of a single edge. A kite system of order \(n\) is a pair \((X,K)\), where \(K\) is a collection of edge disjoint kites which partitions the edge set of \(K_n\) (= the complete undirected graph on \(n\) vertices) with vertex set \(X\). Let \((X,B)\) be a block design with block size 4. If we remove a path of length 2 from each block in \(B\), we obtain a partial kite-system. If the deleted edges can be assembled into kites the result is a kite system, called a \emph{metamorphosis} of the block design \((X,B)\). There is an obvious extension of this definition to \(\lambda\)-fold block designs with block size 4. In this paper we give a complete solution of the following problem: Determine all pairs \((\lambda, n)\) such that there exists a \(\lambda\)-fold block design of order \(n\) with block size 4 having a metamorphosis into a \(\lambda\)-fold kite system.
We introduce the concept of equal chromatic partition of networks. This concept is useful for deriving lower bounds and upper bounds for performance ratios of dynamic tree embedding schemes that arise in a wide range of tree-structured parallel computations. We provide necessary and sufficient conditions for the existence of equal chromatic partitions of several classes of interconnection networks which include \(X\)-Nets, folded hypercubes, \(X\)-trees, \(n\)-dimensional tori and \(k\)y \(n\)-cubes. We use the pyramid network as an example to show that some networks do not have equal chromatic partitions, but may have near-equal chromatic partitions.
Let \(X_1,X_2,X_3,X_4\) be four type 1 \((1,-1)\) matrices on the same group of order \(n\) (odd) with the properties: (i) \((X_i – I)^T = -(X_i – I)\), \(i=1,2\), (ii) \(X_i^T = X_i\), \(i = 3,4\) and the diagonal elements are positive, (iii) \(X_iX_j = X_jX_i\), and (iv) \(X_1X_1^T + X_2X_2^T + X_3X_3^T + X_4X_4^T = 4nI_n\). Call such matrices \(G\)-matrices. If there exist circulant \(G\)-matrices of order \(n\) it can be easily shown that \(4n – 2 = a^2 + b^2\), where \(a\) and \(b\) are odd integers. It is known that they exist for odd \(n \leq 27\), except for \(n = 11,17\) for which orders they can not exist. In this paper we give for the first time all non-equivalent circulant \(G\)-matrices of odd order \(n \leq 33\) as well as some new non-equivalent circulant \(G\)-matrices of order \(n = 37,41\). We note that no \(G\)-matrices were previously known for orders 31, 33, 37 and 41. These are presented in tables in the form of the corresponding non-equivalent supplementary difference sets. In the sequel we use \(G$-matrices to construct some \(F\)-matrices and orthogonal designs.
The clique graph \(K(G)\) of a given graph \(G\) is the intersection graph of the collection of maximal cliques of \(G\). Given a family \(\mathcal{F}\) of graphs, the \({clique-inverse \;graphs}\) of \(\mathcal{F}\) are the graphs whose clique graphs belong to \(\mathcal{F}\). In this work, we describe characterizations for clique-inverse graphs of bipartite graphs, chordal bipartite graphs, and trees. The characterizations lead to polynomial time algorithms for the corresponding recognition problems.
We prove that the domination number of every graph of diameter 2 on \(n\) vertices is at most \(\left(\frac{1}{\sqrt{2}} + o(1)\right) \sqrt{n \log n}\) as \(n \to \infty\) (with logarithm of base \(e\)). This result is applied to prove that if a graph of order \(n\) has diameter 2, then it contains a spanning caterpillar whose diameter does not exceed \(\left(\frac{3}{\sqrt{2}} + o(1)\right) \sqrt{n \log n}\). These estimates are tight apart from a multiplicative constant, since there exist graphs of order \(n\) and diameter 2, with domination number not smaller than \(\left(\frac{1}{2\sqrt{2}} + o(1)\right) \sqrt{n \log n}\). In contrast, in graphs of diameter 3, the domination number can be as large as \(\lfloor \frac{n}{2} \rfloor\) (but not larger).
Our results concerning diameter 2 improve the previous upper bound of \(O(n^{3/4})\), published by Faudree et al. in [Discuss. Math. Graph Theory 15 (1995), 111-118].
As an extension of the fractional domination and fractional domatic graphical parameters, multi-fractional domination parameters are introduced. We demonstrate the Linear Programming formulations, and to these formulations we apply the Partition Class Theorem, which is a generalization of the Automorphism Class Theorem. We investigate some properties of the multi-fractional domination numbers and their relationships to the fractional domination and fractional domatic numbers.
In a graph, the Steiner distance of a set of vertices \(U\) is the minimum number of edges in a connected subgraph containing \(U\). For \(k \geq 2\) and \(d \geq k-1\), let \(S(k,d)\) denote the property that for all sets \(S\) of \(k\) vertices with Steiner distance \(d\), the Steiner distance of \(S\) is preserved in any induced connected subgraph containing \(S\). A \(k\)-Steiner-distance-hereditary (\(k\)-SDH) graph is one with the property \(S(k, d)\) for all \(d\). We show that property \(S(k, k)\) is equivalent to being \(k\)-SDH, and that being \(k\)-SDH implies \((k + 1)\)-SDH. This establishes a conjecture of Day, Oellermann and Swart.
The quantity \(g^{(k)}(v)\) was introduced in [4] as the minimum number of blocks necessary in a pairwise balanced design on \(v\) elements, subject to the condition that the longest block have cardinality \(k\). When \(k \geq (v – 1)/2\), it is known that \(g^{(k)}(v) = 1 + (v – k)(3k – v + 1)/2\), except for the case when \(v \equiv 1 \pmod{4}\) and \(k = (v – 1)/2\). This exceptional “case of first failure” was treated in [1] and [2]. In this paper, we discuss the structure of the “case of first failure” for the situation when \(v = 4s + 4\).
We construct some codes, designs and graphs that have the first or second Janko group, \(J_1\) or \(J_2\), respectively, acting as an automorphism group. We show computationally that the full automorphism group of the design or graph in each case is \(J_1\), \(J_2\) or \(\bar{J}_2\), the extension of \(J_2\) by its outer automorphism, and we show that for some of the codes the same is true.
A 3-regular graph \(G\) is called a 3-circulant if its adjacency matrix \(A(G)\) is a circulant matrix. We show how all disconnected 3-circulants are made up of connected 3-circulants and classify all connected 3-circulants as one of two basic types. The rank of \(A(G)\) is then completely determined for all 3-circulant graphs \(G\).
The independence number \(\beta_n\), for knights on equilateral triangular boards \(T_n\), of regular hexagons is determined for all \(n\).
It was conjectured by Lee that a cubic simple graph with \(4k + 2\) vertices is edge-magic [5]. In this paper we show that the conjecture is not true for multigraphs or disconnected simple graphs in general. Several new classes of cubic edge-magic graphs are exhibited.
In 1976 Erdős asked about the existence of Steiner triple systems that lack collections of \(j\) blocks employing just \(j+2\) points. This has led to the study of anti-Pasch, anti-mitre and 5-sparse Steiner triple systems. Simultaneously generating sets and bases for Steiner triple systems and \(t\)-designs have been determined. Combining these ideas, together with the observation that a regular graph is a 1-design, we arrive at a natural definition for the girth of a design. In turn, this provides a natural extension of the search for cages to the universe of all \(t\)-designs. We include the results of computational experiments that give an abundance of examples of these new definitions.
A graph \(G\) is called an \(L_1\)-graph if, for each triple of vertices \(x, y,\) and \(z\) with \(d(x,y) = 2\) and \(z \in N(x) \cap N(y)\), \(d(x) + d(y) \geq |N(x) \cup N(y) \cup N(z)| – 1\). Let \(G\) be a \(3\)-connected \(L_1\)-graph of order \(n \geq 18\). If \(\delta(G) \geq n/3\), then every pair of vertices \(u\) and \(v\) in \(G\) with \(d(u,v) \geq 3\) is connected by a Hamiltonian path of \(G\).
How many vertices must we delete from a graph so that it no longer contains a path \(P_k\) on \(k\) vertices? We explore this question for various special graphs (hypercubes, square lattice graphs) as well as for some general families.
A complete list is given of all finite trivalent arc-transitive connected graphs on up to \(768\) vertices, completing and extending the Foster census. Several previously undiscovered graphs appear, including one on \(448\) vertices which is the smallest arc-transitive trivalent graph having no automorphism of order 2 which reverses an arc. The graphs on the list are classified according to type (as described by Djokovic and Miller in terms of group amalgams), and were produced with the help of a parallel program which finds all normal subgroups of low index in a finitely-presented group. Further properties of each graph are also given: its girth, diameter, Hamiltonicity, and whether or not it is bipartite.
In this paper the decomposition of Dyck words into a product of Dyck prime subwords is studied. The set of Dyck words which are decomposed into \(k\) components is constructed and its cardinal number is evaluated.
For an ordered set \(W = \{w_1, w_2, \ldots, w_k\}\) of vertices and a vertex \(v\) in a graph \(G\), the representation of \(v\) with respect to \(W\) is the \(k\)-vector \(r(v|W) = (d(v, w_1), d(v, w_2), \ldots, d(v, w_k))\), where \(d(x,y)\) represents the distance between the vertices \(x\) and \(y\). The set \(W\) is a resolving set for \(G\) if distinct vertices of \(G\) have distinct representations. A resolving set containing a minimum number of vertices is called a basis for \(G\) and the number of vertices in a basis is the (metric) dimension \(\dim G\). A connected graph is unicyclic if it contains exactly one cycle. For a unicyclic graph \(G\), tight bounds for \(\dim G\) are derived. It is shown that all numbers between these bounds are attainable as the dimension of some unicyclic graph.
It is an established fact that some graph-theoretic extremal questions play an important part in the investigation of communication network vulnerability. Questions concerning the realizability of graph invariants are generalizations of the extremal problems. We define a \((p,q, \kappa,\delta)\) graph as a graph having \(p\) vertices, \(q\) edges, vertex connectivity \(\kappa\) and minimum 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,4, \delta), (p, \Delta,\delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability, where \(\Delta\) denotes the maximum degree for all vertices in a graph and \(\lambda\) denotes the edge connectivity of a graph.
Upper and lower bounds are given for the toughness of generalized Petersen graphs. A lower bound of \(1\) is established for \(t(G(n,k))\) for all \(n\) and \(k\). This bound of \(1\) is shown to be sharp if \(n = 2k\) or if \(n\) is even and \(k\) is odd. The upper bounds depend on the parity of \(k\). For \(k\) odd, the upper bound \(\frac{n}{n-\frac{n+1}{2}}\) is established. For \(k\) even, the value \(\frac{2k}{2k-1}\) is shown to be an asymptotic upper bound. Computer verification shows the reasonableness of these bounds for small values of \(n\) and \(k\).
Suppose \(G\) is a graph. The minimum number of paths (trees, forests, linear forests, star forests, complete bipartite graphs, respectively) needed to decompose the edges of \(G\) is called the path number (tree number, arboricity, linear arboricity, star arboricity and biclique number, respectively) of \(G\). These numbers are denoted by \(p(G), t(G), a(G), la(G), sa(G), r(G)\), respectively. For integers \(1 \leq k \leq n\), let \(C_{n,k}\) be the graph with vertex set \(\{a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n\}\) and edge set \(\{a_ib_j :i=1,2,\ldots ,n,j \equiv i+1,i+2, \ldots ,i+k \text{(mod n)}\}\). We call \(C_{n,k}\) a crown. In this paper, we prove the following results:
Due to (3), (4), we propose the following conjectures.
\(\textbf{Conjecture A}\). For \(3 \leq k \leq n-1\),
\[sa(C_{n,k}) = \begin{cases}
\left\lceil \frac{k}{2} \right\rceil + 1 & \text{if \(k\) is odd}, \\
\left\lceil \frac{k}{2} \right\rceil + 2 & \text{if \(k\) is even}.
\end{cases}\]
\(\textbf{Conjecture B}\). For \(1 \leq k \leq n-1\), \(r(C_{n,k}) = n\).
Let \(G = (V, E)\) be a graph and \(A\) a non-trivial Abelian group, and let \(\mathcal{F}(G, A)\) denote the set of all functions \(f: E(G) \to A\). Denote by \(D\) an orientation of \(E(G)\). Then \(G\) is \(A\)-colorable if and only if for every \(f \in \mathcal{F}(G, A)\) there exists an \(A\)-coloring \(c: V(G) \to A\) such that for every \(e = (x,y) \in E(G)\) (assumed to be directed from \(x\) to \(y\)), \(c(x) – c(y) \neq f(e)\). If \(G\) is a graph, we define its group chromatic number \(\chi_1(G)\) to be the minimum number \(m\) for which \(G\) is \(A\)-colorable for any Abelian group \(A\) of order \(\geq m\) under the orientation \(D\). In this paper, we investigated the properties of the group chromatic number, proved the Brooks Type theorem for \(\chi_1(G)\), and characterized all bipartite graphs with group chromatic number at most \(3\), among other things.
A signed graph is an unoriented graph with a given partition \(E = E^+ \bigcup E^-\) of its edge-set. We define the arc signed graph \({A}(G)\) of an oriented graph \(G\) (G has no multiple arcs, opposite arcs, and loops). The arc signed graphs are similar to the line graphs. We prove both a Krausz-type characterization and a forbidden induced subgraph characterization (like the theorem of Beineke and Robertson on line graphs). Unlike line graphs, there are infinitely many minimal forbidden induced subgraphs for the arc signed graphs. Nevertheless, the arc signed graphs are polynomially recognizable. Also, we obtain a result similar to Whitney’s theorem on line graphs.
For a vertex \(v\) in a graph \(G\), we denote by \(N^2(v)\) the set \((N_1(N_1(v))\setminus \{v\})\cup N_1(v)=\{x\in V(G): 1 \leq d(x,v) \leq 2\}\), where \(d(x,v)\) denotes the distance between \(x\) and \(v\). A vertex \(v\) is \(N^2\)-locally connected if the subgraph induced by \(N^2(v)\) is connected. A graph \(G\) is called \(N^2\)-locally connected if every vertex of \(G\) is \(N^2\)-connected. A well-known result by Oberly and Sumner is that every connected locally connected claw-free graph on at least three vertices is Hamiltonian. This result was improved by Ryjacek using the concept of second-type neighborhood. In this paper, using the concept of \(N^2\)-locally connectedness, we show that every connected \(N^2\)-locally connected claw-free graph \(G\) without vertices of degree \(1\), which does not contain an induced subgraph \(H\) isomorphic to one of \(G_1, G_2, G_3\), or \(G_4\), is Hamiltonian, hereby generalizing the result of Oberly and Sumner (J. Graph Theory, \(3 (1979) 351-356\))and the result of \(Ryjacek\)( J. Graph Theory, \(14 (1990)\) 321-381)
On the gracefulness of graph \(C_m\bigcup P_n\), Frucht and Salinas that proved \(C_m\bigcup P_n\) is graceful and conjectured: \(C_m\bigcup P_n\) is graceful if and only if \(m+n=7\). In this paper, we prove graph \(C_m\bigcup P_n\) is graceful, for \(m=4k, n=k+2, k+3, 2k+1,\ldots, 2k+5;\) \(m=4k+1, n=2k, 3k+1, 4k+1;\) \(m=4k+2 n=3k, 3k+1,
4k+1; m=4k+3, n=2k+1, 3k, 4k\).
Let \(\nu(\mathbb{Z}^m)\) be the minimal number of colors enough to color the \(m\)-dimensional integer grid \(\mathbb{Z}^m\) so that there would be no infinite monochromatic symmetric subsets. Banakh and Protasov [3] compute \(\nu(\mathbb{Z}^m) = m+1\). For the one-dimensional case this just means that one can color positive integers in red, while negative integers in blue, thereby avoiding an infinite monochromatic symmetric subset by a trivial reason. This motivates the question what changes if we allow only colorings unlimited in both directions (in “all” directions for \(m > 1\)). In this paper we show that then \(\nu(\mathbb{Z})\) increases by \(1\), whereas for higher dimensions the values \(\nu(\mathbb{Z}^m)\) remain unaffected.
Furthermore we examine the density properties of a set \(A \subseteq \mathbb{Z}^m\) that ensure the existence of infinite symmetric subsets or arbitrarily large finite symmetric subsets in \(A\). In the case that \(A\) is a sequence with small gaps, we prove a multi-dimensional analogue of the Szemerédi theorem, with symmetric subsets in place of arithmetic progressions. A similar two-dimensional statement is known for collinear subsets (Pomerance [10]), whereas for two-dimensional arithmetic progressions even the corresponding version of van der Waerden’s theorem is known to be false.
The eccentricity of a vertex \(v\) in a connected graph \(G\) is the distance between \(v\) and a vertex farthest from \(v\). For a vertex \(v\), we define the edge-added eccentricity of \(v\) as the minimum eccentricity of \(v\) in all graphs \(G+e\), taken over all edges \(e\) in the complement of \(G\). A graph is said to be edge-added stable (or just stable) if the eccentricity and the edge-added eccentricity are the same for all vertices in the graph. This paper describes properties of edge-added eccentricities and edge-added stable graphs.
In this paper, we find explicit formulas or generating functions for the cardinalities of the sets \(S_n(T,\tau)\) of all permutations in \(S_n\) that avoid a pattern \(\tau \in S_k\) and a set \(T, |T| \geq 2,\) of patterns from \(S_3\). The main body of the paper is divided into three sections corresponding to the cases \(|T| = 2, 3\) and \(|T| \geq 4\). As an example, in the fifth section, we obtain the complete classification of all cardinalities of the sets \(S_n(T,\tau)\) for \(k = 4\).
The concept of weakly associative lattices (i.e. relational systems with a reflexive and antisymmetric relation \(\leq\), in which for each pair of elements there exist a least upper and a greatest lower bound) was introduced in [3] and [5]. In [4] WU-systems are defined, i.e. weakly associative lattices with the unique bound property, and their equivalence with projective planes is described. In this paper we introduce WU\(_{\lambda}\)-systems, and discuss their relation to symmetric \(2\)-\((v,k,\lambda)\) designs equipped with a special “loop-free” mapping.
It is shown in this paper that every \(2\)-connected claw-free graph containing a \(k\)-factor has a connected \([k,k+1]\)-factor, where \(k \geq 2\).
Let \(G\) be a graph of order \(n\), and let \(n = \sum_{i=1}^{k}a^i\) be a partition of \(n\) with \(a_i \geq 2\). Let \(v_1, \ldots, v_k\) be given distinct vertices of \(G\). Suppose that the minimum degree of \(G\) is at least \(3k\). In this paper, we prove that there exists a decomposition of the vertex set \(V(G) = \bigcup_{i=1}^k A_i\) such that \(|A_i| = a_i\), \(v_i \in A_i\), and the subgraph induced by \(A_i\) contains no isolated vertices for all \(i, 1 \leq i \leq k\).
Let \(G\) be a graph of order \(n \geq 4k\) and let \(S\) be the graph obtained from \(K_4\) by removing two edges which have a common vertex. In this paper, we prove the following theorem:
A graph \(G\) of order \(n \geq 4k\) with \(\sigma_2(G) \geq n+k\) has \(k\) vertex-disjoint \(S\).This theorem implies that a graph \(G\) of order \(n = 4k\) with \(\sigma_2(G) \geq 5k\) has an \(S\)-factor.
The reconstruction number \(rn(G)\) of graph \(G\) is the minimum number of vertex-deleted subgraphs of \(G\) required in order to identify \(G\) up to isomorphism. Myrvold and Molina have shown that if \(G\) is disconnected and not all components are isomorphic then \(rn(G) = 3\), whereas, if all components are isomorphic and have \(c\) vertices each, then \(rn(G)\) can be as large as \(c + 2\). In this paper we propose and initiate the study of the gap between \(rn(G) = 3\) and \(rn(G) = c + 2\). Myrvold showed that if \(G\) consists of \(p\) copies of \(K_c\), then\(rn(G) = c + 2\). We show that, in fact, this is the only class of disconnected graphs with this value of \(rn(G)\). We also show that if \(rn(G) \geq c + 1\) (where \(c\) is still the number of vertices in any component), then, again, \(G\) can only be copies of \(K_c\). It then follows that there exist no disconnected graphs \(G\) with \(c\) vertices in each component and \(rn(G) = c + 1\). This poses the problem of obtaining for a given \(c\), the largest value of \(t = t(c)\) such that there exists a disconnected graph with all components of order \(c\), isomorphic and not equal to \(K_c\), and is such that \(rn(G) = t\).
We take a special \(1\)-factorization of \(K_{n,n}\), and investigate the subgraphs suborthogonal to the \(1\)-factorization. Some interesting results are obtained, including an identity involving \(n^n\) and \(n!\) and a property of permutations.
An extended Mendelsohn triple system of order \(v\) (EMTS(\(v\))) is a collection of cyclically ordered triples of the type \([x,y,z], [x,x,y]\), or \([x,x,x]\) chosen from a \(v\)-set, such that each ordered pair (not necessarily distinct) belongs to exactly one triple. If such a design with parameters \(v\) and \(a\) exist, then they will have \(b_{v,a}\) blocks, where \(b_{v,a} = (v^2 + 2a)/3\). In this paper, we show that there are two (not necessarily distinct) EMTS(\(v\))’s with common triples in the following sets:
\(\{0,1,2,\ldots,b_v-4,b_v-2,b_v\}\), if \(v \neq 6\); and
\(\{0,1,2,\ldots,b_v-4,b_v-2\}\), if \(v = 6\),
where \(b_v\) is \(b_{v,v-1}\) if \(v \equiv 2 \pmod{3}\); \(b_{v,v}\) if \(v \not\equiv 2 \pmod{3}\).
Dudeney’s round table problem was proposed about one hundred years ago. It is already solved when the number of people is even, but it is still unsettled except for only a few cases when the number of people is odd.
In this paper, a solution of Dudeney’s round table problem is given when \(n = p+2\), where \(p\) is an odd prime number such that \(2\) is the square of a primitive root of \(\mathrm{GF}(p)\), and \(p \equiv 3 \pmod{4}\).
The number \(g^{(4)}_{2}\) is the minimal number of blocks that contain all pairs from a set of \(8\) elements exactly twice under the restriction that the longest block has size \(4\) (this longest block need not be unique). Thus the blocks have lengths \(2, 3\), and \(4\). We show that there are three solutions to this problem.
The \(n \times n\) primitive nearly reducible Boolean matrices whose \(k\)-exponents (\(1 \leq k \leq n\)) achieve the maximum value are characterized.
A graph is said to be \(k\)-covered if for each edge \(xy\), \(deg(x) = k\) or \(deg(y) = k\). In this paper, we characterize the \(3\)-covered quadrangulations of closed surfaces.
A graceful graph with \(n\) edges and \(n+1\) vertices is called a vertex-saturated graph. Each graceful graph corresponds to a vertex-saturated graph. Four classes of graceful graphs associated with vertex-saturated graphs are presented. Three of which generalize the results of [1], [2] and [5].
We correct an earlier theorem and reprove its consequences regarding \(c\)-BRDs with \(v \equiv 5, 8 \pmod{12}\). The original conclusions remain valid.
The type of a vertex \(v\) in a \(p\)-page book-embedding is the \(p \times 2\) matrix of nonnegative integers
\[{r}(v) =
\left(
\begin{array}{ccccc}
l_{v,1} & r_{v,1} \\
. & . \\
. & . \\
. & . \\
l_{v,p} & r_{v,p} \\
\end{array}
\right),\]
where \(l_{v,i}\) (respectively, \(r_{v,i}\)) is the number of edges incident to \(v\) that connect on page \(i\) to vertices lying to the left (respectively, to the right) of \(v\). The type number of a graph \(G\), \(T(G)\), is the minimum number of different types among all the book-embeddings of \(G\). In this paper, we disprove the conjecture by J. Buss et al. which says for \(n \geq 4\), \(T(L_n)\) is not less than \(5\) and prove that \(T(L_n) = 4\) for \(n \geq 3\).
Let \(T\) be a chemical tree, i.e. a tree with all vertices of degree less than or equal to \(4\). We find relations for the \(0\)-connectivity and \(1\)-connectivity indices \({}^0\chi(T)\) and \({}^1\chi(T)\), respectively, in terms of the vertices and edges of \(T\). A comparison of these relations with the coefficients of the characteristic polynomial of \(T\) associated to its adjacency matrix is established.
Given a regular action of a finite group \(G\) on a set \(V\), we consider the problem of the existence of an incidence structure \(\mathcal{I} = (V, \mathcal{B})\) on the set \(V\) whose full automorphism group \(Aut(\mathcal{I})\) is the group \(G\) in its regular action. Using results on graphical and digraphical regular representations \(([2,7], [1])\), we show the existence of such an incidence structure for all but four small finite groups.
For a finite field \({F} = {F}(q)\), where \(q = p^n\) is a prime power, we will introduce the notion of equivalence of subsets of \(F\) which stems out of the equivalence of cyclic difference sets, and give the formulae for the number of equivalence classes of \(k\)-subsets of \(F\) as well as for the number of equivalence classes of subsets of \(F\) by using Pólya’s theorem of counting.
We present an algorithmic construction of anti-Pasch Steiner triple systems for orders congruent to \(9\) mod \(12\). This is a Bose-type method derived from a particular type of \(3\)-triangulations generated from non-sum-one-difference-zero sequences (\(NS1D0\) sequences). We introduce \(NS1D0\) sequences and describe their basic properties; in particular, we develop an equivalence between the problem of finding \(NS1D0\) sequences and a variant of the \(n\)-queens problem. This equivalence, and an algebraic characterization of the \(NS1D0\) sequences that produce anti-Pasch Steiner triple systems, form the basis of our algorithm.
For vertices \(u\) and \(v\) in a nontrivial connected graph \(G\), the closed interval \([u,v]\) consists of \(u\), \(v\), and all vertices lying in some \(u-v\) geodesic of \(G\). For \(S \subseteq V(G)\), the set \(I[S]\) is the union of all sets \(I[u,v]\) for \(u,v \in S\). A set \(S\) of vertices of a graph \(G\) is a geodetic set in \(G\) if \(I[S] = V(G)\). The minimum cardinality of a geodetic set in \(G\) is its geodetic number \(g(G)\). A subset \(T\) of a minimum geodetic set \(S\) in a graph \(G\) is a forcing subset for \(S\) if \(S\) is the unique minimum geodetic set containing \(T\). The forcing geodetic number \(f(S)\) of \(S\) in \(G\) is the minimum cardinality of a forcing subset for \(S\), and the upper forcing geodetic number \(f^+(G)\) of the graph \(G\) is the maximum forcing geodetic number among all minimum geodetic sets of \(G\). Thus \(0 \leq f^+(G) \leq g(G)\) for every graph \(G\). The upper forcing geodetic numbers of several classes of graphs are determined. It is shown that for every pair \(a,b\) of integers with \(0 \leq a \leq b\) and \(b \geq 1\), there exists a connected graph \(G\) with \(f^+(G) = a\) and \(g(G) = b\) if and only if \((a, b) \notin \{(1, 1), (2,2)\}\).
Let \(\lambda DK_v\). denote the complete directed multigraph with \(v\). vertices, where any two distinct vertices \(x\). and \(y\). are joined by \(\lambda\). arcs \((x,y)\). and \(\lambda\). arcs \((y,x)\).. By a \(k\).-circuit we mean a directed cycle of length \(k\).. In this paper, we consider the problem of constructing maximal packings and minimal coverings of \(\lambda DK_v\). with \(k\).-circuits. Using the leave-arcs graph of packing and the repeat-arcs graph of covering, we give a unified method for finding packings and coverings. Also, we completely solve the existence of optimal packings and coverings for \(5 \leq k \leq 14\). and any \(\lambda\).
We present necessary and sufficient conditions for the decomposition of \(\lambda\) times the complete directed digraph, \(D_v^{\lambda}\), into each of the orientations of a \(4\)-cycle. In our constructions, we also give necessary and sufficient conditions for such decompositions which admit cyclic or rotational automorphisms.
In this paper, a genetic algorithm and a tabu search are investigated for the maximum satisfiability problem. When the evolutionary algorithm is hybridized with the randomized procedure G-bit [14], better performance is achieved and it even outperforms the well-known probabilistic procedure GSAT [25]. On the other hand, when the random noise strategy is introduced in the tabu search, the latter competes with GSAT with walk [27] independently of the length of the tabu list. The basic result we can argue from this study is that the robustness of a method seems to be bound to the degree of `randomness’ involved in it, but at the expense of the running time. According to the experiments, GSAT and the genetic algorithm are more powerful than tabu search in its simplest form because they incorporate more `randomness’. GSAT with random walk is even more interesting than simple GSAT for the same reason. Also, heuristic methods and local search become more efficient when a random strategy such as a noise is introduced to deviate the search from its usual rules.
A vertex \(x\) of a graph \(G\) resolves two vertices \(u\) and \(v\)of \(G\) if the distance from \(x\) to \(u\) does not equal the distance from \(x\) to \(v\). A set \(S\) of vertices of \(G\) is a resolving set for \(G\) if every two distinct vertices of \(G\)are resolved by some vertex of \(S\). The minimum cardinality of a resolving set for \(G\)is called the metric dimension of \(G\). The problem of finding the metric dimension of a graph is formulated as an integer programming problem. It is shown how a relaxation of this problem leads to a linear programming problem and hence to a fractional version of the metric dimension of a graph. The linear programming dual of this problem is considered and the solution to the corresponding integer programming problem is called the metric independence of the graph. It is shown that the problem of deciding whether, for a given graph \(G\), the metric dimension of \(G\)equals its metric independence is NP-complete. Trees with equal metric dimension and metric independence are characterized. The metric independence number is established for various classes of graphs.
A snake in a graph is a simple cycle without chords. A snake-in-the-box is a snake in the \(n\)-dimensional cube \(Q_n\). Combining the methods of G. Zemor (Combinatorica 17 (1997), 287-298) and of F.I. Solov’eva (Diskret Analiz. 45 (1987), 71-76) a new upper bound for the length of a snake-in-the-box is derived for \(16 \leq n \leq 19081\).
In a graph, a set \(D\) is an \(n\)-dominating set if for every vertex \(x\), not in \(D\), \(x\) is adjacent to at least \(n\) vertices of \(D\). The \(n\)-domination number, \(\gamma_n(G)\), is the order of a smallest \(n\)-dominating set. When this concept was first introduced by Fink and Jacobson, they asked whether there existed a function \(f(n)\), such that if \(G\) is any graph with minimum degree at least \(n\), then \(\gamma_n(G) < \gamma_{f(n)}(G)\). In this paper we show that \(\gamma_2(G) < \gamma_5(G)\) for all graphs with minimum degree at least \(2\). Further, this result is best possible in the sense that there exist infinitely many graphs \(G\) with minimum degree at least \(2\) having \(\gamma_2(G) = \gamma_4(G)\).
Inclusive connectivity parameters for a given vertex in a graph \(G\) are measures of how close that vertex is to being a cutvertex. Thus they provide a local measure of graph vulnerability. In this paper we provide bounds on the inclusive connectivity parameters in \(K_2 \times G\) and inductively extend the results to a certain generalized hypercube.
In this paper, the maximum graphical structure is obtained when the number of vertices p of a connected graph G and tenacity \(T(G) = T\) are given. Finally, the method of constructing the sort of graphs is also presented.
Let \(G\) be a bipartite graph with bipartite sets \(V_1\) and \(V_2\). If \(f\) is a bijective function from the vertices and edges of \(G\) into the first \(p+q\) positive integers, where \(p\) and \(q\) denote the order and size of \(G\), respectively, meeting the properties that \(f\) is a super edge magic labeling and if the cardinal of \(V_i\) is \(p_i\) for \(i=1,2\), then the image of the set \(V_1\) is the set of the first \(p_i\) positive integers and the image of the set \(V_2\) is the set of integers from \(p_1 + 1\) up to \(p\). If a bipartite graph \(G\) admits an special super edge magic labeling, we say that \(G\) is special super edge magic. Some properties of special super edge magic graphs are presented. However, this work is mainly devoted to the study of the relations existing between super edge magic and special super edge magic labelings.
In this note, we present necessary conditions for decomposing \(\lambda K_n\) into copies of \(K_{2,5}\), and show that these conditions are sufficient except for \(\lambda = 5\) and \(n = 8\), and possibly for the following cases: \(\lambda = 1\) and \(n = 40\); and \(\lambda = 3\) and \(n = 16\) or \(20\).
We obtain \(135\) nonisomorphic nearly Kirkman triple systems of order \(18\) (the smallest order for which such a system exists), including all \(119\) systems of a well-defined subclass.
In overloaded task systems, it is by definition not possible to complete all tasks by their deadlines. However, it may still be desirable to maximize the number of in-time task completions. The performance of on-line schedulers with respect to this metric is investigated here. It is shown that in general, an on-line algorithm may perform arbitrarily poorly as compared to clairvoyant (off-line) schedulers. This result holds for general task workloads where there are no constraints on task characteristics. For a variety of constrained workloads that are representative of many practical applications, however, on-line schedulers that do provide a guaranteed level of performance are presented.
We present a new algorithm for computer searches for orthogonal designs. Then we use this algorithm to find new sets of sequences with entries from \(\{0,\pm a, \pm b, \pm c,\pm d\}\) on the commuting variables \(a, b, c, d\) with zero autocorrelation function.
Consider the hit polynomial of the path \(P_{2n}\) embedded in the complete graph \(K_{2n}\). We give a combinatorial interpretation of the \(n\)-th Bessel polynomial in terms of a modification of this hit polynomial, called the ordered hit polynomial. Also, the first derivative of the \(n\)-th Bessel polynomial is shown to be the ordered hit polynomial of \(P_{2n-1}\) embedded in \(K_{2n}\).
In a packer-spoiler game on a graph, two players jointly construct a maximal partial \(F\)-packing of the graph according to some rules, where \(F\) is some given graph. The packer wins if all the edges are used up and the spoiler wins otherwise. The question of which graphs are wins for which player generalizes the questions of which graphs are \(F\)-packable and which are randomly \(F\)-packable. While in general such games are NP-hard to solve, we provide partial results for \(F = P_3\) and solutions for \(F = 2K_2\).
Let G be a \((p,q)\)-graph with p vertices and q edges. An edge-labeling assignment \(\text{L : E} \to \text{N}\) is a map which assigns a positive integer to each edge in E. The induced map \(\text{L}^+ : \text{V} \to \text{N}\) defined by \(\text{L}^+\text{(v)} = \Sigma\{\text{L(u,v) : for all (u,v) in E}\}\) is called the vertex sum. The edge labeling assignment is called \underline{magic} if \(\text{L}^+\) is a constant map. If L is a bijection with \(\text{L(E)} = \{1,2,\ldots,\text{q}\}\) and L is magic then we say L is supermagic. B. M. Stewart showed that \(\text{K}_5\) is not supermagic and when \(\text{n} \equiv 0 \pmod{4}\) , \(\text{K}_\text{n}\) is not supermagic. In this paper, we exhibit supermagicness for a class of regular complete k-partite graphs.
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:
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.
In this paper, we investigate the total colorings of the join graph \(G_1 + G_2\) where \(G_1 \cup G_2\) is a graph with maximum degree at most \(2\). As a consequence of the main result, we prove that if \(G = (2l+1)C_m + (2l+1)C_n\), then \(G\) is Type 2 if and only if \(m = n\) and \(n\) is odd, where \((2l+1)C_m\) and \((2l+1)C_n\) represent \((2l+1)\) disjoint copies of \(C_m\) and \(C_n\), respectively.
In this paper, the standard basis for trades is used to develop an algorithm to classify all simple \(2-(8,3)\) trades. The existence of a total number of \(15,011\) trades reveals the rich structure of trades in spite of a small number of points. Some results on simple \(2-(9, 3)\) trades are also obtained.
We describe an algorithm for finding smallest defining sets of designs. Using this algorithm, we show that the 104 \(STS(19)\) which have automorphism group order at least 9 have smallest defining set sizes in the range 18-23. The numbers of designs with smallest defining sets of \(18, 19, 20, 21, 22\) and \(23\) blocks are, respectively, \(1, 2, 17, 68, 14\) and \(2\).
In this paper, three simple algorithms for the satisfiability problem are presented with their probabilistic analyses. One algorithm, called counting, is designed to enumerate all the solutions of an instance of satisfiability. The second one, namely E-SAT, is proposed for solving the corresponding decision problem. Both the enumeration and decision algorithms have a linear space complexity and a polynomial average time performance for a specified class of instances. The third algorithm is a randomized variant of E-SAT. Its probabilistic analysis yields a polynomial average time performance.
For any abelian group \*A\), we call a graph \(G = (V, E)\) as A-magic if there exists a labeling I: E(G) \(\to \text{A} – \{0\}\) such that the induced vertex set labeling \(I^+: V(G) \to A\)
\[\text{I}^+\text{(v)} = \Sigma \{ \text{I(u,v) : (u,v) in E(G)} \}\]
is a constant map. We denote the set of all \(A\) such that G is \(A\)-magic by \(AM(G)\) and call it as group-magic index set of \(G\).
Let \((\mathcal{P}, \mathcal{B}, \mathcal{I})\) be an asymmetric \((v, k, \lambda)\) block design. The incidence graph \(G\) of this design is distance-regular, hence belongs to an association scheme. In this paper, we use the algebraic structure of this association scheme to analyse certain symmetric partitions of the incidence structure.
A set with two intersection numbers is a subset \(\mathcal{K} \subseteq \mathcal{P}\) with the property that \(|{B} \cap \mathcal{K}|\) takes on only two values as \({B}\) ranges over the blocks of the design. In the special case where the design is a projective plane, these objects have received considerable attention. Two intersection theorems are proven regarding sets of this type which have a certain type of dual. Applications to the study of substructures in finite projective spaces of dimensions two and three are discussed.
In this paper, necessary and sufficient conditions for the existence of a 5-cycle system of the \(\lambda\)-fold complete graph of order \(v\) with a hole of size \(u\),\(\lambda(K_v – K_u)\), are proved.
Let \(G\) be a simple connected graph on \(2n\) vertices with a perfect matching. For a positive integer \(k\), \(1 \leq k \leq n – 1\), \(G\) is \(k\)-\({extendable}\) if for every matching \(M\) of size \(k\) in \(G\), there is a perfect matching in \(G\) containing all the edges of \(M\). For an integer \(k\), \(0 \leq k \leq n – 2\), \(G\) is \({strongly \;k-extendable}\) if \(G\) – \(\{u, v\}\) is \(k\)-extendable for every pair of vertices \(u\) and \(v\) of \(G\). The problem that arises is that of characterizing \(k\)-extendable graphs and strongly \(k\)-extendable graphs. The first of these problems has been considered by several authors whilst the latter has only been recently studied by the author. In a recent paper, we established a number of properties of strongly \(k\)-extendable graphs including some sufficient conditions for strongly \(k\)-extendable graphs. In this paper, we focus on a necessary condition, in terms of minimum degree, for strongly \(k\)-extendable graphs. Further, we determine the set of realizable values for minimum degree of strongly \(k\)-extendable graphs. A complete characterization of strongly \(k\)-extendable graphs on \(2n\) vertices for \(k = n – 2\) and \(n – 3\) is also established.
In this paper we discuss some designs that have been used to train mediators for dispute resolution and tabulate some small examples.
The spectrum \(Q(k,\lambda)\) of coset difference arrays has played an important role in Lu’s work on asymptotic existence of resolvable balanced incomplete block designs. In this article, we use Weil’s theorem on character sums to show that if \(k = 2\lambda + 1\), then for any prime power \(q \equiv 1+2k \pmod{4k}\), \(q \in Q(k,\lambda)\) whenever \(g > D(k) = (\frac{B+\sqrt{B^2+4C}}{2})^2\), where \(B = (k-2)k(2k-1)(2k)^{k-1} – (2k)^{k} + 1\) and \(C = \frac{(k-2)(k-1)}{2}(2k)^{k-1}\). In particular, we determine the spectrum \(Q(3,1)\). In addition, the degenerate case when \(k = \lambda + 1\) is also discussed.
The third author proved earlier [8] that if a Euclidean space is colored with red and blue so that the distance one is forbidden for blue, and translates of some \(k\)-point configuration are forbidden for red, then the unit-distance chromatic number of the space is no greater than \(k\). Here we give a generalization.
We continue the study of graphs defined by a certain adjacency property by investigating the \(n\)-existentially closed line-critical graphs. We classify the \(1\)-e.c. line-critical graphs and give examples of \(2\)-e.c. line-critical graphs for all orders \(\geq 9\).
An isometric path is merely any shortest path between two vertices. Inspired by the game of `Cops and Robber’ and a result by Aigner \(\&\) Fromme [1], we are interested in determining the minimum number of isometric paths required to cover the vertices of a graph. We find a lower bound on this number in terms of the diameter of a graph and find the exact number for trees and grid graphs.
An edge-graceful \((p, q)\)-graph \(G = (V, E)\) is a graph with \(p\) vertices and \(q\) edges for which there is a bijection \(f : E \to \{1,2,\ldots,q\}\) such that the induced mapping \(f^+ : V \to \mathbb{Z}_p\), defined by \(f^+(u) \equiv \sum\limits_{uv \in E} f(uv) \pmod{p}\), for \(u \in V\), is a bijection. In this paper, some results on edge-gracefulness of trees are extended to \(k\)-fold graphs based on graphs with \(p\) vertices and \(p – 1\) edges. A \(k\)-fold multigraph \(G[k]\) derived from a graph \(G\) is one in which each edge of \(G\) has been replaced by \(k\) parallel edges with the same vertices as the original edge. Certain classes of \(k\)-fold multigraphs derived from paths, combs, and spiders are shown to be edge-graceful, as well as other graphs constructed by combining these graphs in specified ways.
We determine solutions to the problem of gossiping in minimum time (briefly: minimum time problem or MTP) which require less calls than the previously known solutions for infinitely many values of the number \(n\) of persons and optimal solutions to the MTP, i.e. solutions of the MTP which minimize the number of calls, for some values of \(n\). We conjecture that our methods provide optimal solutions of the MTP for all \(n\).
Erdős and Gallai (1963) showed that any \(r\)-regular graph of order \(n\), with \(r < n-1\), has chromatic number at most \({3n}/{5}\), and this bound is achieved by precisely those graphs with complement equal to a disjoint union of 5-cycles.
We are able to generalize this result by considering the problem of determining a \((j-1)\)-regular graph \(G\) of minimum order \(f(j)\) such that the chromatic number of the complement of \(G\) exceeds \({f(j)}/{2}\). Such a graph will be called an \(F(j)\)-\({graph}\). We produce an \(F(j)\)-graph for all odd integers \(j \geq 3\) and show that \(f(j) = {5(j – 1)}/{2}\) if \(j \equiv 3 \pmod{4}\), and \(f(j) = 1 + {5(j – 1)}/{2}\) if \(j \equiv 1 \pmod{4}\).
A lemma of Enomoto, Llado, Nakamigawa and Ringel gives an upper bound for the edge number of a super edge-magic graph with \(p > 1\) vertices. In this paper we give some results which come out from answering some natural questions suggested by this useful lemma.
The scheme associated with a graph is an association scheme if and only if the graph is strongly regular. Consider the problem of extending such an association scheme to a superscheme in the case of a colored, directed graph. The obstacles can be expressed in terms of \(t\)-vertex conditions. If a graph does not satisfy the \(t\)-vertex condition, a prescheme associated with it cannot be erected beyond the \((t-3)\)rd-level.
A mandatory representation design MRD \((K; v)\) is a pairwise balanced design PBD \((K; v)\) in which for each \(k \in K\) there is at least one block in the design of size \(k\). The study of the mandatory representation designs is closely related to that of subdesigns in pairwise balanced designs. In this paper, we survey the known results on MRDs and pose some open questions.
It is shown that the necessary conditions are sufficient for the existence of all \(c\)-BRDs\((v, 3, \lambda)\) for negative \(c\)-values. This completes the study of \(c\)-BRDs with block size three as previously the authors and J. Seberry have shown that the necessary conditions are sufficient for \(c \geq -1\).
Let \(G\) be a simple connected graph on \(2n\) vertices with a perfect matching. For a positive integer \(k\), \(1 \leq k \leq n-1\), \(G\) is \(k\)-\emph{extendable} if for every matching \(M\) of size \(k\) in \(G\), there is a perfect matching in \(G\) containing all the edges of \(M\). For an integer \(k\), \(0 \leq k \leq n – 2\), \(G\) is \emph{strongly \(k\)-extendable} if \(G – \{u, v\}\) is \(k\)-extendable for every pair of vertices \(u\) and \(v\) of \(G\). The problem that arises is that of characterizing \(k\)-extendable graphs and strongly \(k\)-extendable graphs. The first of these problems has been considered by several authors whilst the latter has been investigated only for the case \(k = 0\). In this paper, we focus on the problem of characterizing strongly \(k\)-extendable graphs for any \(k\). We present a number of properties of strongly \(k\)-extendable graphs including some necessary and sufficient conditions for strongly \(k\)-extendable graphs.
In this paper we count the number of non-homeomorphic continua in a certain collection of continua. The continua in these collections are trees with certain restrictions on them. We refer to a continuum in one of these collections as a caterpillar continuum.
The convex polyhedron of all real-valued monotone functions defined on a finite poset is an unbounded variant of the order polytope described by Stanley. If the undirected covering graph of the poset is acyclic, then the lattice of non-empty faces of this polyhedron is a Boolean lattice. In every other case, both semimodularity and dual semimodularity fail.
In a paper of Cockayne et al., the authors establish an upper and a lower bound for the dominating number of the complete grid graph \(G_{n,n}\), of order \(n^2\). Namely, they proved a “formula”, and cited two questions of Paul Erdős. One of these questions was “Can we improve the order of the difference between lower and upper bounds from \(\frac{n}{5}\) to \(\frac{n}{2}\)?”. Our aim here is to give a positive answer to this question.
Let \(D = (V_1, V_2; A)\) be a directed bipartite graph with \(|V_1| = |V_2| = n \geq 2\). Suppose that \(d_D(x) + d_D(y) \geq 3n\) for all \(x \in V_1\) and \(y \in V_2\). Then, with one exception, \(D\) contains two vertex-disjoint directed cycles of lengths \(2s\) and \(2t\), respectively, for any two positive integers \(s\) and \(t\) with \(s+t \leq n\).
The edge clique graph of a graph \(G\) is one having as vertices the edges of \(G\), two vertices being adjacent if the corresponding edges of \(G\) belong to a common clique.
Recently, Hsu and Shiue [10] obtained a kind of generalized Stirling number pairs with three free parameters and proved some of its properties. Here, some properties analogous to those of ordinary Stirling numbers are investigated, viz. horizontal recurrence relations, vertical recurrence relations, rational generating function, and explicit formulas. Furthermore, a kind of infinite sum which is useful in some combinatorial applications of the generalized Stirling numbers, is evaluated.
Clique graphs of several classes of graphs have been already characterized. Trees, interval graphs, chordal graphs, block graphs, clique-Helly graphs are some of them. However, no characterization of clique graphs of circular-arc graphs and some of their subclasses is known. In this paper, we present a characterization theorem of clique graphs of Helly circular-arc graphs and prove that this subclass of circular-arc graphs is properly contained in the intersection between proper circular-arc graphs, clique-Helly circular-arc graphs and Helly circular-arc graphs. Furthermore, we prove properties about the \(2^{\text{nd}}\) iterated clique graph of this family of graphs.
Let \(g: \mathbb{F}^m \to \mathbb{F}\) be a linear function on the vector space \(\mathbb{F}^m\) over a finite field \(\mathbb{F}\). A subset \(S \subsetneqq \mathbb{F}\) is called \(g\)-thin iff \(g(S^m) \subsetneqq \mathbb{F}\). In case \(\mathbb{F}\) is the field \(\mathbb{Z}_p\) of odd prime order, if \(S\) is \(g\)-thin and if \(m\) divides \(p-1\), then it is shown that \(|S| \leq \frac{p-1}{m}\). We also show that in certain cases \(S\) must be an arithmetic progression, and the form of the linear function \(g\) can be characterized.
A family \(\mathcal{F}\) of finite sets is said to have property \(B\) if there exists a set \(S\) such that \(0 < |{S} \cap F| < |F|\) for all \(F \in \mathcal{F}\). Denote by \(m_N(n)\) the least integer \(m\) for which there exists a family \(\mathcal{F}\) of \(m\) \(n\)-element subsets of a set \(V\) of size \(N\) such that \(\bigcup \mathcal{F} = V\) and which does not have property \(B\). We give constructions which yield upper bounds for \(m_N(4)\) for certain values of \(N\).
Let \(G\) be a connected graph and \(\mathcal{V}^*\) the set of all spanning trees except stars in \(G\). An edge in a spanning tree is called `inner’ if the edge is not incident to endvertices. Define an adjacency relation in \(\mathcal{V}^*\) as follows: two spanning trees \(t_1\) and \(t_2 \in \mathcal{V}^*\) are called to be adjacent if there exist inner edges \(e_i \in E(t_i)\) such that \(t_1 – e_1 = t_2 – e_2\). The resultant graph is a subgraph of the tree graph, and we call it simply a trunk graph. The purpose of this paper is to show that if a \(2\)-connected graph with at least five vertices is \(k\)-edge connected, then its trunk graph is \((k-1)\)-connected.
Let \(\tau(n)\) denote Ramanujan’s tau function. We obtain an identity that involves \(\tau(n)\) and \(\sigma(n)\), as well as some apparently new congruence properties of \(\tau(n)\) with respect to the moduli \(23\) and \(5\).
For loopless multigraphs \(G\), the total choice number is asymptotically equal to its fractional counterpart as the latter invariant tends to infinity. If \(G\) is embedded in the plane, then the edge-face and entire choice numbers exhibit the same “asymptotically good” behaviour. These results are based mainly on an analogous theorem of Kahn [5] for the list-chromatic index. Together with work of Kahn and others, our three results give a complete answer to a natural question: which of the seven invariants associated with list-colouring the nonempty subsets of \(\{V, E, F\}\) are asymptotically good?
In 1970, Behzad, Chartrand and Wall conjectured that the girth of every \(r\)-regular digraph \(G\) of order \(n\) is at most \(\left\lceil \frac{n}{r} \right\rceil\). The conjecture follows from a theorem of Menger and Dirac if \(G\) has strong connectivity \(x = r\). We show that any digraph with minimum in-degree and out-degree at least \(r\) has girth at most \(\left\lceil \frac{n}{r} \right\rceil\) if \(\kappa = r – 1\). We also find from the literature a family of counterexamples to a conjecture of Seymour.
In this paper, we give an alternative proof for the fact that the graph obtained by overlapping the cycle \(C_m\) (\(m \geq 3\)) and the complete bipartite graph \(K_{2,s}\) (\(s \geq 1\)) at an edge is uniquely determined by its chromatic polynomial. This result provides a partial solution to a question raised in [7].
Let \(G\) be a simple graph with \(n\) vertices. \(p(G,k)\) denotes the number of ways in which one can select \(k\) independent edges in \(G\) (\(k \geq 1\)). Let \(p(G,0) = 1\) for all \(G\).
The matching polynomial \(\alpha(G)\) of a graph \(G\) is given by:
\[\alpha(G) = \alpha(G,x) = \sum_{k=0}^{\left[\frac{n}{2}\right]} (-1)^k p(G,k) x^{n-2k}\]
In this article, we give the matching polynomials of the complete \(n\)-partite graph with a differential operator.
The List Edge Coloring Conjecture states that for every graph, the chromatic index equals the choice index. We prove the conjecture for outerplanar graphs with maximum degree at least five.
Cycle prefix digraphs are a class of Cayley coset graphs with many remarkable properties, such as:Symmetry Large number of nodes for a given degree and diameter Simple shortest path routing Hamiltonicity Optimal connectivity Others.
In this paper, we show that the cycle prefix digraphs, like the Kautz digraphs, contain cycles of all lengths \(l\), with \(l\) between two and \(N\), the order of the digraph, except for \(N-1\).
Let \(G\) be a cubic bipartite plane graph that has a perfect matching. If \(M\) is any perfect matching of \(G\), then \(G\) has a face that is \(M\)-alternating.If \(f\) is any face of \(G\), then there is a perfect matching \(M\) such that \(f\) is \(M\)-alternating.There is a simple algorithm for visiting all perfect matchings of \(G\) beginning at one.
There are infinitely many cubic plane graphs that have perfect matchings but whose matching transformation graphs are completely disconnected.
Several problems are proposed.
In this paper, we calculate the jump number of the product of an ordered set and a chain.
In [1], [2] we can find results concerning kernel-perfect graphs and solvable graphs. These concepts are related to kernels of a digraph. The authors of [2] consider two graph constructions: the join of two graphs and duplication of a vertex. These kinds of graphs preserve kernel-perfectness and solvability of their orientations. In this paper we generalize results from [2] applying them to \((k,l)\)-kernels and two operations: generalized join and duplication of a subset of vertices. The concept of a \((k,l)\)-kernel of a digraph was introduced in [8] and was studied in [6], [7], and [9]. In our considerations we take advantage of the asymmetrical part of digraphs, which was used by H. Galeana-Sanchez in [6] in the proof of a sufficient condition for a digraph to have a \((k, l)\)-kernel.
With the help of computer algorithms, we improve the lower bound on the Ramsey multiplicity of \(K_4\) and thus show that the exact value of it is equal to \(9\).
For two integers \(k > 0\) and \(s (\geq 0\)), a cycle of length \(s\) is called an \((s \mod k)\)-cycle if \(l \equiv s \mod k\). In this paper, the following conjecture of Chen, Dean, and Shreve [5] is proved:Every \(2\)-connected graph with at least six vertices and minimum degree at least three contains a (\(2 \mod 4\))-cycle.
In this paper we present graceful and nearly graceful labelings of some graphs. In particular, we show, graceful labelings of the \(kC_4-snake\) (for the general case),\(kC_6\) and \(kC_{12}-snakes\) (for the even case),and also establish some conditions to obtain graceful labelings of \(kC_{4n}-snakes\) with some related results. Moreover, for the linear \(kC_6\)-snake, we show:a graceful labeling when \(k\) is even,a nearly graceful labeling when \(k\) is odd.We also explore the connection of these labelings with more restrictive variations of graceful ones.
By considering the order of the largest induced bipartite subgraph of \(G\), Hagauer and Klaviar [4] were able to improve the bounds first published by V. G. Vizing [6] for the independence number of the Cartesian product \(G \Box H\) for any graph \(H\). In this paper, we study maximum independent sets in \(G \Box H\) when \(G\) is a caterpillar, and derive bounds for the independence number when \(H\) is bipartite. The upper bound we produce is less than or equal to that in [4] when \(H\) is also a caterpillar, and is shown to be strictly smaller when \(H\) comes from a restricted class of caterpillars.
Let \(T\) be a spanning tree of a graph \(G\). This paper is concerned with the following operation: we remove an edge \(e \in E(T)\) from \(T\), and then add an edge \(f \in E(G) – E(T)\) so that \(T – e + f\) is a spanning tree of \(G\). We refer to this operation of obtaining \(T – e + f\) from \(T\) as the transfer of \(e\) to \(f\). We prove that if \(G\) is a \(2\)-connected graph with \(|V(G)| \geq 5\), and if \(T_1\) and \(T_2\) are spanning trees of \(G\) which are not stars, then \(T_1\) can be transformed into \(T_2\) by repeated applications of a transfer of a nonpendant edge (an edge \(xy\) of a tree \(T\) is called a nonpendant edge of \(T\) if both of \(x\) and \(y\) have degree at least \(2\) in \(T\)).
We provide upper estimates on the weak exponent of indecomposability of an irreducible Boolean matrix.
The toughness \(t(G)\) of a noncomplete graph \(G\) is defined as
\[t(G) = \min\left\{\frac{|S|}{\omega(G-S)} \mid S \subseteq 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 middle graph \(M(G)\) of a graph \(G\) is the graph obtained from \(G\) by inserting a new vertex into every edge of \(G\) and by joining by edges those pairs of these new vertices which lie on adjacent edges of \(G\).
In this article, we give the toughness of the middle graph of a graph, and using this result we also give a sufficient condition for the middle graph to have a \(k\)-factor.
This paper gives constructions of balanced incomplete block designs and group divisible designs with \(k = 7, 8,\) or \(9\), and \(\lambda = 1\). The first objective is to give constructions for all possible cases with the exception of \(40, 78,\) and \(157\) values of \(v\). Many of these initial exceptions have now been removed by Abel. In an update section, more are removed; group divisible designs with groups of size \(k(k-1)\) are constructed for \(k = 7\) and \(8\) with \(124\) and \(87\) exceptions; it is also established that \(v \geq 294469\) and \(v \equiv 7\) mod \(42\) suffices for the existence of a resolvable balanced incomplete block design with \(k = 7\). Group divisible designs with group size \(k\) and resolvable designs are constructed.
A connected graph \(G = (V, E)\) is \((a, d)\)-antimagic if there exist positive integers \(a, d\) and a bijection \(g: E \to \{1, 2, \ldots, |E|\}\) such that the induced mapping
\[f_g = \Sigma\{g(u,v): (u, v) \in E(G)\}\, \text{is injective and}\]
\[f_g(V) = \{a, a+d, a+2d, \ldots, a+(|V|-1)d\}.\]
In this paper, we prove two conjectures of Baca concerning \((a, d)\)-antimagic labelings of antiprisms
Some special sum graphs and difference graphs, based on abelian groups, are discussed. In addition to Li’s result on character sum estimates, Weil’s character sum estimates are also used to show that these are indeed Ramanujan graphs.
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\). A smallest critical set in a Latin square is a critical set of minimum cardinality. In this paper we find smallest critical sets for all the Latin squares of orders six and seven. We also find smallest critical sets of orders six and seven which are also weak critical sets. In particular, we find a weak critical set of size twelve for the dihedral group of order six.
We study combinatorial structure of \(\ell\)-optimal \(A^2\)-codes that offer the best protection for spoofing of order up to \(\ell\) and require the least number of keys for the transmitter and the receiver. We prove that for such codes the transmitter’s encoding matrix is a strong partially balanced resolvable design, and the receiver’s verification matrix corresponds to an \(\alpha\)-resolvable design with special properties.
It is proved in this paper that for any integer \(n \geq 136\), a SODLS(\(v, n\)) (self-orthogonal diagonal Latin square with missing subsquare) exists if and only if \(v \geq 3n+2\) and \(v-n\) even.
Employing trading signed design algorithm, we construct an automorphism-free \(4\)-\((15, 5, 5)\) design.
Consider those graphs \(G\) of size \(2n\) that have an eigenvalue \(\lambda\) of multiplicity \(n\) and where the edges between the star set and its complement is a matching. We show that \(\lambda\) must be either \(0\) or \(1\) and completely characterize the corresponding graphs.
We enumerate the 2-\((9,4,6)\) designs and find \(270,474,142\) non-isomorphic such designs in a backtrack search. The sizes of their automorphism groups vary between \(1\) and \(360\). Out of these designs, \(19,489,464\) are simple and \(2,148,676\) are decomposable.
A \(t\)-partite number is a \(t\)-tuple \(\vec{n} = (n_1, \ldots, n_t)\), where \(n_1, \ldots, n_t\) are positive integers. For a \(t\)-partite number \(\vec{n}\), let \(f_t(\vec{n})\) be the number of different ways to write \(\vec{n}\) as a product of \(t\)-partite numbers, where the multiplication is performed coordinate-wise, \((1, 1, \ldots, 1)\) is not used as a factor of \(\vec{n}\), and two factorizations are considered the same if they differ only in the order of the factors. This paper gives the following explicit upper bound for the multiplicative partition function \(f_t(\vec{n})\):
\[f_t(n_1, \ldots, n_t) \leq M^{w(t)},\, \text{where}\,\, M = \Pi_{i=1}^t n_i \,\,\text{and}\,\, w(t) = \frac{\log((t+1)1)}{t\log2}\].
The following partition problem was first introduced by R.C. Entringer and has subsequently been studied by the first author and more recently by Bollobas and Scott, who consider the hypergraph version as well, using a probabilistic technique. The partition problem is that of coloring the vertex set of a graph with \(s\) colors so that the number of induced edges is bounded for each color class. The techniques employed are non-constructive and non-probabilistic and improve the known bounds in the previous papers.
In a communication network, several vulnerability measures are used to determine the resistance of the network to disruption of operation after the failure of certain stations or communication links. If we think of a graph as modeling a network, the edge-integrity of a graph is one \(\textbf{measure of graph vulnerability}\) and it is defined to be the minimum sum of the orders of a set of edges being removed and a largest remaining component. In this paper, the edge-integrity of graphs \(B_n\), \(H_n\), and \(E_p^t\), are calculated. Also, some results are given about edge-integrity of these graphs.
In this paper, it is shown that the necessary condition for the existence of a holey perfect Mendelsohn design (HPMD) with block size 5, type \(h^n\) and index \(\lambda\), namely, \(n \geq 5\) and \(\lambda n(n-1)h^2 \equiv 0 \pmod{5}\), is also sufficient for \(\lambda \geq 2\). The result guarantees the analogous existence result for group divisible designs (GDDs) of type \(h^n\) having block size 5 and index \(4\lambda\).
The computational complexity of the graph isomorphism problem is still unknown. We consider Cartesian products \(K_n \times K_m\) of two complete graphs \(K_n\) and \(K_m\). An acyclic orientation of such a Cartesian product is called a sequence graph because it has an application in production scheduling. It can be shown that the graph isomorphism problem on the class of these acyclic digraphs is solvable in polynomial time. We give numbers of non-isomorphic sequence graphs for small \(n\) and \(m\). The orientation on the cliques of a sequence graph can be interpreted as job orders and machine orders of a shop scheduling problem with a complete operation set.
Tenacity is a recently introduced parameter to measure vulnerability of networks and graphs. We characterize graphs having the maximum number of edges among all graphs with a given number of vertices and tenacity.
In this paper, we show that some graphs are circuit unique by applying a new tool, which is the character of the matching polynomial. Some properties of the character of the matching polynomial is also given.
The theory of hypergeometric functions is brought to bear on a problem—namely, that of obtaining a certain power series expansion involving the sine function that is inclusive of the Catalan sequence and which serves as a prelude to the calculation of other related series of similar type. A general formulation provides the particular result of interest as a special case, into which Catalan numbers are introduced as desired.
A splitting partition for a graph \(G = (V, E)\) is a partition of \(V\) into sets \(R\), \(B\), and \(U\) so that the subgraphs induced by \(V – R\) and \(V – B\) are isomorphic. The splitting number \(\mu(G)\) is the size of \(|R|\) for any splitting partition which maximizes \(|R|\). This paper determines \(\mu(G)\) for trees of maximum degree at most three and exactly one degree two vertex and for trees all of whose vertices have degree three or one.
A decomposition of a digraph is said to be bicyclic if it admits an automorphism consisting of exactly two disjoint cycles. Necessary and sufficient conditions are given for the existence of bicyclic decompositions of the complete digraph into each of the four orientations of a 4-cycle.
The integrity of a graph \(G\), \(I(G)\), is defined by \(I(G) = min_{S \subseteq V(G)}\{|S| + m(G – S)\}\) where \(m(G – S)\) is the maximum order of the components of \(G – S\). In general, the integrity of an \(r\)-regular graph is not known [8]. We answer the following question for special regular graphs. For any given two integers \(p\) and \(r\) such that \(\frac{pr}{2}\) is an integer, is there an \(r\)-regular graph, say \(G^*\), on \(p\) vertices having size \(q = \frac{pr}{2}\) such that
\[I(G(p,\frac{pr}{2})) \leq I(G^*)\]
for all \(p\) and \(r\)? The \({integrity\; graph}\) is denoted by \(IG(p,n)\). It is a graph with \(p\) vertices, integrity \(n\), and has the least number of edges denoted by \(q[p,n]\). We compute \(q[p,n]\) for some values of \(p,n\).
If the distance between two vertices \(u\) and \(v\) in a graph \(G\) is \(k\), then \(u\) and \(v\) are said to \(k\)-step dominate each other. A set \(S\) of vertices of \(G\) is a \(k\)-step dominating set if every vertex of \(G\) is \(k\)-step dominated by some vertex of \(S\). The minimum cardinality of a \(k\)-step dominating set is the \(k\)-step domination number \(\rho_k(G)\) of \(G\). A sequence \(s: \ell_1, \ell_2, \ldots, \ell_k\) of positive integers is called an orbital dominating sequence for \(G\) if there exist distinct vertices \(v_1, v_2, \ldots, v_k\) of \(G\) such that every vertex of \(G\) is \(\ell_i\)-step dominated by \(v_i\) for some \(i\) (\(1 \leq i \leq k\)). An orbital dominating sequence \(s\) is minimal if no proper subsequence of \(s\) is an orbital dominating sequence for \(G\). The minimum length of a minimal orbital dominating sequence is the orbital domination number \(\gamma_{o}(G)\), while the maximum length of such a sequence is the upper orbital domination number \(\Gamma_{o}(G)\) of \(G\).
It is shown that for every pair \(i, j\) of positive integers with \(i < j\), there exist graphs \(G\) and \(H\) such that both \(\rho_i(G) – \rho_j(G)\) and \(\rho_j(H) – \rho_i(H)\) are arbitrarily large. Also, there exist graphs \(G\) of arbitrarily large radius such that \(\gamma_{o}(G) < \rho_i(G)\) for every integer \(i\) (\(1 \leq i \leq \text{rad} G\)). All trees \(T\) with \(\gamma_{o}(T) = 3\) are characterized, as are all minimum orbital sequences of length 3 for graphs. All graphs \(G\) with \(\Gamma_{o}(G) = 2\) are characterized, as are all trees \(T\) with \(\Gamma_{o}(T) = 3\).
A Gray code is a list of words such that each word differs from its successor by a number of letters which is bounded independently of the length of the word. We use Roelants van Baronaigien’s I-code for involutions to derive a Gray code for all length-\(n\) involutions and one for those with a given number of length-2 cycles. In both Gray codes, each involution is transformed into its successor via one or two transpositions or a rotation of three elements. For both Gray codes we obtain algorithms for passing between a word and its position in the list and a non-recursive sequencing algorithm (transforming a given word into its successor or determining that it is the last word in the list) which runs in \(O(n)\) worst-case time and uses \(O(1)\) auxiliary variables; for involutions with a given number of length-2 cycles we also obtain a sequencing algorithm which runs in \(O(1)\) worst-case time and uses \(O(n)\) auxiliary variables. We generalize Chase’s method for obtaining non-recursive sequencing algorithms to any list of words in which all the words with a given suffix form an interval of consecutive words, and we show that if in addition the letter preceding the suffix always takes at least two distinct values in that interval, then Ehrlich’s method will find in \(O(1)\) time the rightmost letter in which a word differs from its successor.
In this paper, we obtain critical sets for the general dihedral group, but we are not able to decide whether they are minimal. We also show the existence of a weakly completable critical set in the latin square based on the dihedral group of order six. We believe this to be the smallest group-based square to have such a set.
An \(S_h\)-set (mod \(m\)) is a set \(S\) of integers such that the sums\(a_1 + a_2 + \cdots + a_h\) of elements \(a_1 \leq a_2 \leq \cdots 1\) and prove that equality is possible at least when \(h=p\) is a prime (Theorem).
We investigate those classes \(\mathcal{K}\) of relational structures closed under operations that are defined by excluding a fixed class of finite structures. We characterize such classes and show they contain an infinite family of pairwise non-embeddable members. NEC structures are defined by certain extension conditions. We construct countable universal structures in \(\mathcal{K}\) satisfying only finitely many of the NEC extension conditions.
The notion of normal quotient of a vertex-transitive graph was introduced in [5]. It was shown there that many graph properties are inherited by normal quotients. The definition of a normal quotient was given in [5] in group-theoretical terms. In this note we give a combinatorial approximation to this notion which extends the original definition. We show that many of the properties that were inherited by group-theoretical normal quotients are also inherited by combinatorial ones.
A \((k;g)\)-cage is a smallest \(k\)-regular graph with girth \(g\). Harary and Kovacs [2] conjectured that for all \(k \geq 3\) and odd \(g \geq 5\), there exists a \((k;g)\)-cage which contains a cycle of length \(g+1\). Among other results, we prove the conjecture for all \(k \geq 3\) and \(g \in \{5,7\}\).
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\).
In this article, we discuss the toughness of the endline graph of a graph and the middle graph of a graph.
We present several new non-isomorphic one-factorizations of \(K_{36}\) and \(K_{40}\) which were found through hill-climbing and testing Skolem sequences. We also give a brief comparison of the effectiveness of hill-climbing versus exhaustive search for perfect one-factorizations of \(K_{2n}\) for small values of \(2n\).
We prove that all cycles are edge-magic, thus solving a problem presented by [2]. In [3] it was shown that all cycles of odd length are edge-magic. We give explicit constructions that show that all cycles of even length are edge-magic. Our constructions differ for the case of cycles of length \(n \equiv 0 \pmod{4}\) and \(n \equiv 2 \pmod{4}\).
We present results that characterize the covering number and the rank partition of the dual of a matroid \(M\) using properties of \(M\). We prove, in particular, that the elements of covering number \(2\) in \(M^*\) are the elements of the closure of the maximal \(2\)-transversals of \(M\).
From the results presented it can be seen that every matroid \(M\) is a weak map image of a transversal matroid with the same rank partition.
Let \(G\) be a spanning subgraph of \(K_{s,s}\), and let \(H\) be the complement of \(G\) relative to \(K_{s,s}\),; that is, \(K_{s,s} = G \ oplus H\) is a factorization of \(K_{s,s}\). For a graphical parameter \(\mu(G)\), a graph \(G\) is \(\mu(G)\)-critical if \(\mu(G + e) < \mu(G)\) for every \(e\) in the ordinary complement \(\bar{G}\) of \(G\), while \(G\) is \(\mu(G)\)-critical relative to \(K_{s,s}\) if \(\mu(G + e) < \mu(G)\) for all \(e \in E(H)\). We show that no tree \(T\) is \(\mu(T)\)-critical and characterize the trees \(T\) that are \(\mu(T)\)-critical relative to \(K_{s,s}\), where \(\mu(T)\) is the domination number and the total domination number of \(T\).
The star graph \(S_n\) and the alternating group graph \(A_n\) are two popular interconnection graph topologies. \(A_n\) has a higher connectivity while \(S_n\) has a lower degree, and the choice between the two graphs depends on the specific requirement of an application. The degree of \(S_n\) can be even or odd, but the degree of \(A_n\) is always even. We present a new interconnection graph topology, split-star graph \(S^2_{n}\), whose degree is always odd. \(S^2_{n}\) contains two copies of \(A_n\) and can be viewed as a companion graph for \(A_n\). We demonstrate that this graph satisfies all the basic properties required for a good interconnection graph topology. In this paper, we also evaluate \(S_n\), \(A_n\), and \(S^2_{n}\) with respect to the notion of super connectivity and super edge-connectivity.
We construct a small table of lower bounds for the maximum number of mutually orthogonal frequency squares of types \(F(n; \lambda)\) with \(n \leq 100\).
A graph \(G\) is \(\{R, S\}\)-free if \(G\) contains no induced subgraphs isomorphic to \(R\) or \(S\). The graph \(Z_1\) is a triangle with a path of length \(1\) off one vertex; the graph \(Z_2\) is a triangle with a path of length \(2\) off one vertex. A graph that is \(\{K_{1,3}, Z_1\}\)-free is known to be either a cycle or a complete graph minus a matching. In this paper, we investigate the structure of \(\{K_{1,3}, Z_2\}\)-free graphs. In particular, we characterize \(\{K_{1,3}, Z_2\}\)-free graphs of connectivity \(1\) and connectivity \(2\).
The problem is to determine the number of `cops’ needed to capture a `robber’ where the game is played with perfect information with the cops and the robber alternating moves. The `cops’ capture the `robber’ if one of them occupies the same vertex as the robber at any time in the game. Here we show that a graph with strong isometric dimension two requires no more than two cops.
Combinatorial properties of the multi-peg Tower of Hanoi problem on \(n\) discs and \(p\) pegs are studied. Top-maps are introduced as maps which reflect topmost discs of regular states. We study these maps from several points of view. We also count the number of edges
in graphs of the multi-peg Tower of Hanoi problem and in this way obtain some combinatorial identities.
A given nonincreasing sequence \(\mathcal D = (d_1, d_2, \dots, d_n)\) is said to contain a (nonincreasing) repetition sequence \(\mathcal D ^* = (d_{i_1},d_{i_2} \dots, d_{i_k})\) for some \(k \leq n – 2\) if all values of \(\mathcal D – \mathcal D ^*\) are distinct and for any \(d_{i_i} \in \mathcal D ^*\), there exists some \(d_t \in \mathcal D – \mathcal D ^*\) such that \(d_{i_1} = d_t\). For any pair of integers \(n\) and \(k\) with \(n \geq k + 2\), we investigate the existence of a graphic sequence which contains a given repetition sequence. Our main theorem contains the known results for the special case \(d_{i_1} = d_{i_k}\) if \(k = 1\) or \(k = 2\) (see [1, 5, 2]).
It is shown that the necessary conditions are sufficient for the existence of \(c\)-BRD(\(v, 3, \lambda\)) for all \(c \geq -1\). This was previously known for \(c = 0\) and for \(c = 1\).
Let \(\mathcal{S}\) be the set of vectors \(\{{e^{i\theta}}:\theta=0, \frac{n}{3}, \frac{2n}{3}\}\), and let \(\mathcal{S}\) be a nonempty simply connected union of finitely many convex polygons whose edges are parallel to vectors in \(\mathcal{S}\). If every three points of \(\mathcal{S}\) see a common point via paths which are permissible (relative to \(\mathcal{S}\)), then \(\mathcal{S}\) is star-shaped via permissible paths. The number three is best possible.
Let \(G\) be a graph with \(n\) vertices and suppose that for each vertex \(v\) in \(G\), there exists a list of \(k\) colors, \(L(v)\), such that there is a unique proper coloring for \(G\) from this collection of lists, then \(G\) is called a uniquely \(k\)-list colorable graph. Recently, M. Mahdian and E.S. Mahmoodian characterized uniquely \(2\)-list colorable graphs. Here, we state some results which will pave the way in characterization of uniquely \(k\)-list colorable graphs. There is a relationship between this concept and defining sets in graph colorings and critical sets in latin squares.
Let \(d_3(n,k)\) be the maximum possible minimum Hamming distance of a ternary linear \([n, k, d; 3]\) code for given values of \(n\) and \(k\). The nonexistence of \([142, 7, 92; 3]\), \([162, 7, 106; 3]\), \([165, 7, 108; 3]\), and \([191, 7, 125; 3]\) codes is proved.
The niche graph of a digraph \(D\) is the undirected graph defined on the same vertex set in which two vertices are adjacent if they share either a common in-neighbor or a common out-neighbor in \(D\). We define a hierarchy of graphs depending on the condition of being the niche graph of a digraph having, respectively, no cycles, no cycles of length two, no loops, or loops. Our goal is to classify in this hierarchy all graphs of order \(n \geq 3\) having a subgraph isomorphic to \(K_{n-2}\).
Let \(\mathcal{H}_1, \ldots, \mathcal{H}_t\) be classes of graphs. The class Ramsey number \(R(\mathcal{H}_1, \ldots, \mathcal{H}_t)\) is the smallest integer \(n\) such that for each \(t\)-edge colouring \((G_1, \ldots, G_t)\) of \(K_n\), there is at least one \(i \in \{1, \ldots, t\}\) such that \(G_i\) contains a subgraph \(H_i \in \mathcal{H}_i\). We take \(t = 2\) and determine \(R(\mathcal{G}^1_l, \mathcal{G}^1_m)\) for all \(2 \leq l \leq m\) and \(R(\mathcal{G}^2_i, \mathcal{G}^2_{m})\) for all \(3 \leq l \leq m\), where \(\mathcal{G}^i_j\) consists of all edge-minimal graphs of order \(j\) and minimum degree \(i\).
Let \(G\) be a \(2\)-connected graph with a toroidal rotation system given. An algorithm for constructing a straight line drawing with no crossings on a rectangular representation of the torus is presented. It is based on Read’s algorithm for constructing a planar layout of a \(2\)-connected graph with a planar rotation system. It is proved that the method always works. The complexity of the algorithm is linear in the number of vertices of \(G\).
A graph \(G\) is called super-edge-magic if there exists a bijection \(f\) from \(V(G) \cup E(G)\) to \(\{1, 2, \ldots, |V(G)| + |E(G)|\}\) such that \(f(u) + f(v) + f(uv) = C\) is a constant for any \(uv \in E(G)\) and \(f(V(G)) = \{1, 2, \ldots, |V(G)|\}\). In this paper, we show that the generalized Petersen graph \(P(n, k)\) is super-edge-magic if \(n \geq 3\) is odd and \(k = 2\).
We reprove an important case of a recent topological result on improved Bonferroni inequalities due to Naiman and Wynn in a purely combinatorial manner. Our statement and proof involves the combinatorial concept of non-evasiveness instead of the topological concept of contractibility. In contradistinction to the proof of Naiman and Wynn, our proof does not require knowledge of simplicial homology theory.
Quackenbush [5] has studied the properties of squags or “Steiner quasigroups”, that is, the corresponding algebra of Steiner triple systems. He has proved that if a finite squag \((P; \cdot)\) contains two disjoint subsquags \((P_1; \cdot)\) and \((P_2; \cdot)\) with cardinality \(|P_1| = |P_2| = \frac{1}{3} |P|\), then the complement \(P_3 = P – (P_1 \cup P_2)\) is also a subsquag and the three subsquags \(P_1, P_2\) and \(P_3\) are normal. Quackenbush then asks for an example of a finite squag of cardinality \(3n\) with a subsquag of cardinality \(n\), but not normal. In this paper, we construct an example of a squag of cardinality \(3n\) with a subsquag of cardinality \(n\), but it is not normal; for any positive integer \(n \geq 7\) and \(n \equiv 1\) or \(3\) (mod \(6\)).
A plane graph is an embedding of a planar graph into the sphere which may have multiple edges and loops. A face of a plane graph is said to be a pseudo triangle if either the boundary of it has three distinct edges or the boundary of it consists of a loop and a pendant edge. A plane pseudo triangulation is a connected plane graph of which each face is a pseudo triangle. If a plane pseudo triangulation has neither a multiple edge nor a loop, then it is a plane triangulation. As a generalization of the diagonal flip of a plane triangulation, the diagonal flip of a plane pseudo triangulation is naturally defined. In this paper we show that any two plane pseudo triangulations of order \(n\) can be transformed into each other, up to ambient isotopy, by at most \(14n – 64\) diagonal flips if \(n \geq 7\). We also show that for a positive integer \(n \geq 5\), there are two plane pseudo triangulations with \(n\) vertices such that at least \(4n – 15\) diagonal flips are needed to transform into each other.
An extended Mendelsohn triple system of order \(v\) with a idempotent element (EMTS(\(v, a\))) is a collection of cyclically ordered triples of the type \(\{x, y, z\}\), \(\{x, x, y\}\) or \(\{x, x, x\}\) chosen from a \(v\)-set, such that every ordered pair (not necessarily distinct) belongs to only one triple and there are \(a\) triples of the type \(\{x, x, x\}\). If such a design with parameters \(v\) and \(a\) exist, then they will have \(b_{v,a}\) blocks, where \(b_{v,a} = (v^2 + 2a)/3\). A necessary and sufficient condition for the existence of EMTS(\(v, 0\)) and EMTS(\(v, 1\)) are \(v \equiv 0\) (mod \(3\)) and \(v \not\equiv 0\) (mod \(3\)), respectively. In this paper, we have constructed two EMTS(\(v, 0\))’s such that the number of common triples is in the set \(\{0, 1, 2, \ldots, b_{v, 0} – 3, b_{v, 0}\}\), for \(v \equiv 0\) (mod \(3\)). Secondly, we have constructed two EMTS(\(v, 1\))’s such that the number of common triples is in the set \(\{0, 1, 2, \ldots, b_{v, 1} – 2, b_{v, 1}\}\), for \(v \not\equiv 0\) (mod \(3\)).
An edge-colouring of a graph \(G\) is \({equitable}\) if, for each vertex \(v\) of \(G\), the number of edges of any one colour incident with \(v\) differs from the number of edges of any other colour incident with \(v\) by at most one. In the paper, we prove that any outerplanar graph has an equitable edge-colouring with \(k\) colours for any integer \(k \geq 3\).
In this paper we give alternative and shorter proofs of three theorems of Chetwynd and Hilton. All these three theorems have been widely used in many research papers.
The paper defines \((a, d)\)-face antimagic labeling of a certain class of convex polytopes. The possible values of \(d\) are determined as \(d = 2, 4\) or \(6\). For \(d = 2\) and \(4\) we produce \((9n + 3, 2)\) and \((6n + 4, 4)\)-face antimagic labelings for the polytopes.
The domination number \(\gamma(G)\) and the irredundance number \(ir(G)\) of a graph \(G\) have been considered by many authors. It is well known that \(ir(G) \leq \gamma(G)\) holds for all graphs \(G\). In this paper we determine all pairs of connected graphs \((X, Y)\) such that every graph \(G\) containing neither \(X\) nor \(Y\) as an induced subgraph satisfies \(ir(G) = \gamma(G)\).
We consider an inner product of a special type in the space of \(n\)-tuples over a finite field \({F}_q\), of characteristic \(p\). We prove that there is a very close relationship between the self-dual \(q\)-ary additive codes under this inner product and the self-dual \(p\)-ary codes under the usual dot product. We prove the MacWilliams identities for complete weight enumerators of \(q\)-ary additive codes with respect to the new inner product. We define a two-tuple weight enumerator of a binary self-dual code and prove that it is invariant of a group of order 384. We compute the Molien series of this group and find a good polynomial basis for the ring of its invariants.
Let \(G\) be a simple graph with \(n\) vertices, and let \(\overline{G}\) denote the complement of \(G\). A well-known theorem of Nordhaus and Gaddum [6] bounds the sum \(\chi(G) + \chi(\overline{G})\) and product \(\chi(G)\chi(\overline{G})\) of the chromatic numbers of \(G\) and its complement in terms of \(n\). The \emph{edge cost} \(ec(G)\) of a graph \(G\) is a parameter connected with node fault tolerance studies in computer science. Here we obtain bounds for the sum and product of the edge cost of a graph and its complement, analogous to the theorem of Nordhaus and Gaddum.
In this paper we obtain some results on orthogonal arrays \((O-arrays)\) of strength six by considering balanced arrays \((B-arrays)\) of strength six with \(\underline{\mu}’ = (\mu – 1, \mu, \mu, \mu, \mu, \mu, \mu – 1)\) which we call Near O-arrays. As a consequence we demonstrate that we obtain better bounds on the number of constraints for some O-arrays as compared to those given by Rao (1947).
Let \([n, k, d; q]\)-codes be linear codes of length \(n\), dimension \(k\) and minimum Hamming distance \(d\) over \({GF}(q)\). Let \(d_7(n, k)\) be the maximum possible minimum Hamming distance of a linear \([n, k, d; 7]\)-code for given values of \(n\) and \(k\). In this paper, fifty-eight new linear codes over \({GF}(7)\) are constructed, the nonexistence of sixteen linear codes is proved and a table of \(d_7(n,k)\) , \(k\leq7\), \(n\leq100\) is presented.
We study problems related to the number of edges of a graph with diameter constraints. We show that the problem of finding, in a graph of diameter \(k \geq 2\), a spanning subgraph of diameter \(k\) with the minimum number of edges is NP-hard. In addition, we propose some efficient heuristic algorithms for solving this problem. We also investigate the number of edges in a critical graph of diameter 2. We collect some evidence which supports our conjecture that the number of edges in a critical graph of diameter 2 is at most \(\Delta(n-\Delta)\) where \(\Delta\) is the maximum degree. In particular, we show that our conjecture is true for \(\Delta \leq \frac{1}{2}n\) or \(\Delta \geq n-5\).
A digraph \(D\) is reversible if it is isomorphic to the digraph obtained by reversing all arcs of \(D\). A digraph is subreversible if adding any arc between two non-adjacent vertices results in a reversible digraph. We characterize all subreversible digraphs which do not contain cycles of length \(3\) or \(4\).
In this paper we prove that, except for the 4-cycle and the 5-cycle, every 2-connected \(K(1,3)\)-free graph of diameter at most two is pancyclic.
The well-known clique tree representation for chordal graphs is extended to multidimensional representations for arbitrary graphs in which the number of vertices in the representation, minus the number of edges, plus the number of distinguished cycles, minus the number of distinguished polyhedra, and so on, always equals one. This approach generalizes both chordal graphs and cycle spaces of graphs. It also leads to a `dimension’ parameter that is shown to be no greater than the boxicity, chromatic number, and tree-width parameters.
An \(e=1\) function is a function \(f: V(G) \rightarrow [0,1]\) such that every non-isolated vertex \(u\) is adjacent to some vertex \(v\) such that \(f(u) + f(v) = 1\), and every isolated vertex \(w\) has \(f(w) = 1\). A theory of \(e=1\) functions is developed focussing on minimal and maximal \(e=1\) functions. Relationships are traced between \(e=1\) parameters and some well-known domination parameters, which lead to results about classical and fractional domination parameters.
We formulate the construction of 1-rotational difference families as a combinatorial optimization problem. A tabu search algorithm is used to find an optimal solution to the optimization problem for various 1-rotational difference family parameters. In particular, we construct two new 1-rotational difference families which lead to an equal number of new 1-rotational RBIBDs with parameters: \((36, 9, 8)\) and \((40, 10, 9)\). Our algorithm also was able to construct six non-isomorphic \((36, 9, 8)\) and three \((40, 10, 9)\) RBIBDs
For two vertices \(u\) and \(v\) of a connected graph \(G\) , the set \(H(u,v)\) consists of all those vertices lying on a \(u-v\) geodesic in \(G\) . Given a set \(S\) of vertices of \(G\) , the union of all sets \(H(u,v)\) for \(u,v\in S\) is denoted by \(H(S)\) . A convex set \(S\) satisfies \(H(S)=S\) . The convex hull \([S]\) is the smallest convex set containing \(S\) . The hull number \(h(G)\) is the minimum cardinality among the subsets \(S\) of \(V(G)\) with \([S]=V(G)\) . A set \(S\) is a geodetic set if \(H(S)=V(G)\) ; while \(S\) is a hull set if \([S]=V(G)\) . The minimum cardinality of a geodetic set of \(G\) is the geodetic number \(g(G)\) . A subset \(T\) of a minimum hull set \(S\) is called a forcing subset for \(S\) if \(S\) is the unique minimum hull set containing \(T\) . The forcing hull number \(f(S,h)\) of \(S\) is the minimum cardinality among the forcing subsets of \(S\) , and the forcing hull number \(f(G,h)\) of \(G\) is the minimum forcing hull number among all minimum hull sets of \(G\) . The forcing geodetic number \(f(S,g)\) of a minimum geodetic set \(S\) in \(G\) and the forcing geodetic number \(f(G,g)\) of \(G\) are defined in a similar fashion. The forcing hull numbers of several classes of graphs are determined. It is shown that for integers \(a,b\) with \(0\leq a\leq b\) , there exists a connected graph \(G\) such that \(f(G,h)=a\) and \(h(G)=b\) . We investigate the realizability of integers \(a,b\geq0\) that are the forcing hull and forcing geodetic numbers, respectively, of some graph.
Let \(C\) be a perfect 1-error-correcting code of length \(15\). We show that a quotient \(H(C)\) of the minimum distance graph of \(C\) constitutes an invariant for \(C\) more sensible than those studied up to the present, namely the kernel dimension and the rank. As a by-product, we get a nonlinear Vasil’ev code \(C\) all of whose associated Steiner triple systems are linear. Finally, the determination of \(H(C)\) for known families of \(C\)’s is presented.
A computer search shows that there does not exist a nested BIB design \(\text{NB}(10, 15, 2, 3)\).
We construct several families of simple 4-designs, which are closely related to Alltop’s series with parameters \(4-(2^f+1,5,5)\), \(f\) odd. More precisely, for every \(q=2^f\), where \(gcd(f,6)=1\), \(f\geq5\), we construct designs with the following parameters:
\[4-(q+1,6,\lambda),\, \text{where}\, \lambda\in\{60,70,90,100,150,160\},\]
\[4-(q+1,8,35),\]
\[4-(q+1,9,\lambda),\, \text{where}\, \lambda\in\{63,147\}.\]
Eulerian numbers may be defined recursively and have applications to many branches of mathematics. We derive some congruence and divisibility properties of Eulerian numbers.
In this paper, we determine the spectrum of support sizes of indecomposable threefold triple systems of order \(v\) for all \(v > 15\).
A Latin square is \(N_e\) if it has no intercalates (Latin subsquares of order \(2\)). We correct results published in an earlier paper by McLeish, dealing with a construction for \(N_2\) Latin squares.
In [13], we conjectured that if \(G = (V_1, V_2; E)\) is a bipartite graph with \(|V_1| = |V_2| = 2k\) and minimum degree at least \(k + 1\), then \(G\) contains \(k\) vertex-disjoint quadrilaterals. In this paper, we propose a more general conjecture: If \(G = (V_1, V_2; E)\) is a bipartite graph such that \(|V_1| = |V_2| = n \geq 2\) and \(\delta(G) \geq [n/2] + 1\), then for any bipartite graph \(H = (U_1, U_2; F)\) with \(|U_1| \leq n, |U_2| \leq n\) and \(\Delta(H) \leq 2, G\) contains a subgraph isomorphic to \(H\). To support this conjecture, we prove that if \(n = 2k + t\) with \(k \geq 0\) and \(t \geq 3, G\) contains \(k + 1\) vertex-disjoint cycles covering all the vertices of \(G\) such that \(k\) of them are quadrilaterals.
In a finite projective plane, a \(k\)-arc \(\mathcal{K}\) covers a line \(l_0\) if every point on \(l_0\) lies on a secant of \(\mathcal{K}\). Such \(k\)-arcs arise from determining sets of elements for which no linear \((n, q, t)\)-perfect hash families exist [1], as well as from finding sets of points in \(\mathrm{AG}(2, q)\) which determine all directions [2]. This paper provides a lower bound on \(k\) and establishes exactly when the lower bound is attained. This paper also gives constructions of such \(k\)-arcs with \(k\) close to the lower bound.
In this paper we determine the \(k\)-domination number \(\gamma_k\) of \(P_{2k+2} \times P_n\) and \(\lim_{{m,n} \to \infty} \frac{\Gamma_k(P_m \times P_n)}{mn}\).
A digraph obtained by replacing each edge of a complete \(n\)-partite graph by an arc or a pair of mutually opposite arcs is called a semi-complete \(n\)-partite digraph. An \(n\)-partite tournament is an orientation of a complete \(n\)-partite graph. In this paper we shall prove that a strongly connected semicomplete \(n\)-partite digraph with a longest directed cycle \(C\), contains a spanning strongly connected \(n\)-partite tournament which also has the longest directed cycle \(C\) with exception of a well determined family of semicomplete bipartite digraphs. This theorem shows that many well-known results on strongly connected \(n\)-partite tournaments are also valid for strongly connected semicomplete \(n\)-partite digraphs.
Let \(k\) be a positive integer and let \(G\) be a graph. For two distinct vertices \(x, y \in V(G)\), the \(k\)-wide-distance \(d_k(x, y)\) between \(x\) and \(y\) is the minimum integer \(l\) such that there exist \(k\) vertex-disjoint \((x, y)\)-paths whose lengths are at most \(l\). We define \(d_k(x, x) = 0\). The \(k\)-wide-diameter \(d_k(G)\) of \(G\) is the maximum value of the \(k\)-wide-distance between two vertices of \(G\). In this paper we show that if \(G\) is a graph with \(d_k(G) \geq 2\) (\(k \geq 3\)), then there exists a cycle which contains specified \(k\) vertices and has length at most \(2(k – 3)(\operatorname{d_k}(G) – 1) + \max\{3d_k(G), \lfloor\frac{18d_k(G)-16}{5}\rfloor \}\).
Let \(G_1\) and \(G_2\) be two graphs of the same size such that \(V(G_1) = V(G_2)\), and let \(H\) be a connected graph of order at least \(3\). The graphs \(G_1\) and \(G_2\) are \(H\)-adjacent if \(G_1\) and \(G_2\) contain copies \(H_1\) and \(H_2\) of \(H\), respectively, such that \(H_1\) and \(H_2\) share some but not all edges and \(G_2 = G_1 – E(H_1) + E(H_2)\). The graphs \(G_1\) and \(G_2\) are \(H\)-connected if \(G_1\) can be obtained from \(G_2\) by a sequence of \(H\)-adjacencies. The relation \(H\)-connectedness is an equivalence relation on the set of all graphs of a fixed order and fixed size. The resulting equivalence classes are investigated for various choices of the graph \(H\).
A generalized \(p\)-cycle is a digraph whose set of vertices is partitioned in \(p\) parts that are cyclically ordered in such a way that the vertices in one part are adjacent only to vertices in the next part. In this work, we mainly show the two following types of conditions in order to find generalized \(p\)-cycles with maximum connectivity:
1. For a new given parameter \(\epsilon\), related to the number of short paths in \(G\), the diameter is small enough.
2. Given the diameter and the maximum degree, the number of vertices is large enough.
For the first problem it is shown that if \(D \leq 2\ell + p – 2\), then the connectivity is maximum. Similarly, if \(D \leq 2\ell + p – 1\), then the edge-connectivity is also maximum. For problem two an appropriate lower bound on the order, in terms of the maximum and minimum degree, the parameter \(\ell\) and the diameter is deduced to guarantee maximum connectivity.
For a graph \(G = (V, E)\) and \(X \subseteq V(G)\), let \(\operatorname{dist}_G(u, v)\) be the distance between the vertices \(u\) and \(v\) in \(G\) and \(\sigma_3(X)\) denote the minimum value of the degree sum (in \(G\)) of any three pairwise non-adjacent vertices of \(X\). We obtain the main result: If \(G\) is a \(1\)-tough graph of order \(n\) and \(X \subseteq V(G)\) such that \(\sigma_3(X) \geq n\) and, for all \(x, y \in X\), \(\operatorname{dist}_G(x, y) = 2\) implies \(\max\{d(x), d(y)\} \geq \frac{n-4}{2}\), then \(G\) has a cycle \(C\) containing all vertices of \(X\). This result generalizes a result of Bauer, Broersma, and Veldiman.
Some constructions of affine \((\alpha_1, \ldots, \alpha_n)\)-resolvable \((r, \lambda)\)-designs are discussed, by use of affine \(\alpha\)-resolvable balanced incomplete block designs or semi-regular group divisible designs. A structural property is also indicated.
We establish a connection between the principle of inclusion-exclusion and the union-closed sets conjecture. In particular, it is shown that every counterexample to the union-closed sets conjecture must satisfy an improved inclusion-exclusion identity.
Broadcasting in a network is the process whereby information, initially held by one node, is disseminated to all nodes in the network. It is assumed that, in each unit of time, every vertex that has the information can send it to at most one of its neighbours that does not yet have the information. Furthermore, the networks considered here are of bounded (maximum) degree \(\Delta\), meaning that each node has at most \(\Delta\) neighbours. In this article, a new parameter, the average broadcast time, defined as the minimum mean time at which a node in the network first receives the information, is introduced. It is found that when the broadcast time is much greater than the maximum degree, the average broadcast time is (approximately) between one and two time units less than the total broadcast time if the maximum degree is at least three.
The path spectrum, \(\operatorname{sp}(G)\), of a graph \(G\) is the set of all lengths of maximal paths in \(G\). The path spectrum is continuous if \(\operatorname{sp}(G) = \{\ell, \ell1, \dots, \ell\}\) for some \(\ell \leq m\). A graph whose path spectrum consists of a single element is called scent and is by definition continuous. In this paper, we determine when a \(\{K_{1, 3}, S\}\)-free graph has a continuous path spectrum where \(S\) is one of \(C_3, P_4, P_5, P_6, Z_1, Z_2, Z_3, N, B\), or \(W\).
A graph \(G\) is \((p, q, r)\)-choosable if for every list assignment \(L\) with \(|L(v)| \geq p\) for each \(v \in V(G)\) and \(|L(u) \cap L(v)| < p – r\) whenever \(u, v\) are adjacent vertices, \(G\) is \(q\)-tuple \(L\)-colorable. We give an alternative proof of \((4t, t, 3t)\)-choosability for the planar graphs and construct a triangle-free planar graph on \(119\) vertices which is not \((3, 1, 1)\)-choosable (and so neither \(3\)-choosable). We also propose some problems.
We study the behaviour of two domination parameters: the split domination number \(\gamma_s(G)\) of a graph \(G\) and the maximal domination number \(\gamma_m(G)\) of \(G\) after the deletion of an edge from \(G\). The motivation of these problems comes from [2]. In [6] Vizing gave an upper bound for the size of a graph with a given domination number. Inspired by [5] we formulate Vizing type relation between \(|E(G)|, |V(G)|, \Delta(G)\) and \(\delta(G)\), where \(\Delta(G)\) (\(\delta(G)\)) denotes the maximum (minimum) degree of \(G\).
A \(2\)-factor \(F\) of a bipartite graph \(G = (A, B; E)\), \(|A| = |B| = n\), is small if \(F\) comprises \(\lfloor \frac{n}{2}\rfloor\) cycles. A set \(\mathfrak{F}\) of small edge-disjoint \(2\)-factors of \(G\) is maximal if \(G – \mathfrak{F}\) does not contain a small \(2\)-factor. We study the spectrum of maximal sets of small \(2\)-factors.
The linear vertex-arboricity of a graph \(G\) is defined as the minimum number of subsets into which the vertex-set \(V(G)\) can be partitioned so that every subset induces a linear forest. In this paper, we give the upper and lower bounds for the sum and product of linear vertex-arboricity with independence number and with clique cover number, respectively. All of these bounds are sharp.
The independence polynomial of graph \(G\) is the function \(i(G, x) = \sum i_k x^k\), where \(i_k\) is the number of independent sets of cardinality \(k\) in \(G\). We ask the following question: for fixed independence number \(\beta\), how large can the modulus of a root of \(i(G, x)\) be, as a function of \(n\), the number of vertices? We show that the answer is \((\frac{n}{\beta})^{\beta – 1} + O(n^{S-2})\).
Balance has played an important role in the study of random graphs and matroids. A graph is balanced if its average degree is at least as large as the average degree of any of its subgraphs. The density of a non-empty loopless matroid is the number of elements of the matroid divided by its rank. A matroid is balanced if its density is at least as large as the density of any of its submatroids. Veerapadiyan and Arumugan obtained a characterization of balanced graphs; we extend their result to give a characterization of balanced matroids.
We show that there is a straight line embedding of the complete graph \(K_C\) into \(\mathcal{R}^3\) which is space-filling: every point of \(\mathcal{R}^3\) is either one of the vertices of \(K_C\), or lies on exactly one straight line segment joining two of the vertices.
An efficient algorithm for computing chromatic polynomials of graphs is presented. To make very large computations feasible, the algorithm combines the dynamic modification of a computation tree with a hash table to store information from isomorphically distinct graphs that occur during execution. The idea of a threshold facilitates identifying graphs that are isomorphic to previously processed graphs. The hash table together with thresholds allow a table look-up procedure to be used to terminate some branches of the computation tree. This table lookup process allows termination of a branch of the computation tree whenever the graph at a node is isomorphic to a graph that is stored in the hash table. The hashing process generates a large file of graphs that can be used to find any chromatically equivalent graphs that were generated. The initial members of a new family of chromatically equivalent graphs were discovered using this algorithm.
In this paper, we investigate the sufficient conditions for a graph to contain a cycle (path) \(C\) such that \(G\) – \(V(C)\) is a disjoint union of cliques. In particular, sufficient conditions involving degree sum and neighborhood union are obtained.
Let \(k\) and \(d\) be integers with \(d \geq k \geq 4\), let \(G\) be a \(k\)-connected graph with \(|V(G)| \geq 2d – 1\), and let \(x\) and \(z\) be distinct vertices of \(G\). We show that if for any nonadjacent distinct vertices \(u\) and \(v\) in \(V(G) – \{x, z\}\), at least one of \(yu\) and \(zv\) has degree greater than or equal to \(d\) in \(G\), then for any subset \(Y\) of \(V(G) – \{x, z\}\) having cardinality at most \(k – 1\), \(G\) contains a path which has \(x\) and \(z\) as its endvertices, passes through all vertices in \(Y\), and has length at least \(2d – 2\).
For a graph \(G\), a partiteness \(k \geq 2\) and a number of colours \(c\), we define the multipartite Ramsey number \(r^c_k(G)\) as the minimum value \(m\) such that, given any colouring using \(c\) colours of the edges of the complete balanced \(k\)-partite graph with \(m\) vertices in each partite set, there must exist a monochromatic copy of \(G\). We show that the question of the existence of \(r^c_k(G)\) is tied up with what monochromatic subgraphs are forced in a \(c\)-colouring of the complete graph \(K_k\). We then calculate the values for some small \(G\) including \(r^2_3(C_4) = 3, r^2_4(C_4) = 2, r^3_3(C_4) = 7\) and \(r^2_3(C_6) = 3\).
A graph \(G\) with vertex set \(V(G)\) is an exact \(n\)-step domination graph if there is some subset \(S \subseteq V(G)\) such that each vertex in \(G\) is distance \(t\) from exactly one vertex in \(S\). Given a set \(A \subseteq \mathbb{N}\), we characterize cycles \(C_t\) with sets \(S \subseteq V(C_t)\) that are simultaneously \(a\)-step dominating for precisely those \(a \in A\). Using Polya’s method, we compute the number of \(t\)-step dominating sets for a cycle \(C_t\) that are distinct up to automorphisms of \(C_t\). Finally, we generalize the notion of exact \(t\)-step domination.
Let \(D\) be a digraph. The competition-common enemy graph of \(D\) has the same set of vertices as \(D\) and an edge between vertices \(u\) and \(v\) if and only if there are vertices \(w\) and \(x\) in \(D\) such that \((w,u), (w,v), (u,x)\), and \((v,x)\) are arcs of \(D\). We call a graph a CCE-graph if it is the competition-common enemy graph of some digraph. We also call a graph \(G = (V, E)\) CCE-orientable if we can give an orientation \(F\) of \(G\) so that whenever \((w,u), (w,v), (u,x)\), and \((v,x)\) are in \(F\), either \((u,v)\) or \((v,u)\) is in \(F\). Bak \(et\; al. [1997]\) found a large class of graphs that are CCE-orientable and proposed an open question of finding graphs that are not CCE-orientable. In this paper, we answer their question by presenting two families of graphs that are not CCE-orientable. We also give a CCE-graph that is not CCE-orientable, which answers another question proposed by Bak \(et \;al. [1997]\). Finally, we find a new family of graphs that are CCE-orientable.
Let \(G = (V,E)\) be a graph. A set \(S \subseteq V\) is a dominating set if every vertex not in \(S\) is adjacent to a vertex in \(S\). Furthermore, a set \(S \subseteq V\) is a restrained dominating set if every vertex not in \(S\) is adjacent to a vertex in \(S\) and to a vertex in \(V – S\). The domination number of \(G\), denoted by \(\gamma(G)\), is the minimum cardinality of a dominating set, while the restrained domination number of \(G\), denoted by \(\gamma_r(G)\), is the minimum cardinality of a restrained dominating set of \(G\).
We show that if a connected graph \(G\) of order \(n\) has minimum degree at least \(2\) and is not one of eight exceptional graphs, then \(\gamma_r(G) \leq (n – 1)/2\). We show that if \(G\) is a graph of order \(n\) with \(\delta = \delta(G) \geq 2\), then \(\gamma_r(G) \leq n(1 + (\frac{1}{\delta})^\frac{\delta}{\delta-1} – (\frac{1}{\delta})^\frac{1}{\delta-1})\).
Given a two-dimensional text \(T\) and a set of patterns \(\mathcal{D} = \{P_1, \ldots, P_k\}\) (the dictionary), the two-dimensional \({dictionary\; matching}\) problem is to determine all the occurrences in \(T\) of the patterns \(P_i \in \mathcal{D}\). The two-dimensional \({dictionary\; prefix-matching}\) problem is to determine the longest prefix of any \(P_i \in \mathcal{D}\) that occurs at each position in \(T\). Given an alphabet \(\Sigma\), an \(n \times n\) text \(T\), and a dictionary \(\mathcal{D} = \{P_1, \ldots, P_k\}\), we present an algorithm for solving the two-dimensional dictionary prefix-matching problem. Our algorithm requires \(O(|T| + |\mathcal{D}|(log m + log |\Sigma|))\) units of time, where \(m \times m\) is the size of the largest \(P_i \in \mathcal{D}\). The algorithm presented here runs faster than the Amir and Farach [3] algorithm for the dictionary matching problem by an \(O(log k)\) factor. Furthermore, our algorithm improves the time bound that can be achieved using the Lsuffix tree of Giancarlo [6],[7] by an \(O(k)\) factor.
A connected graph \(G = (V, E)\) is said to be \((a, d)\)-antimagic if there exist positive integers \(a, d\) and a bijection \(g: E \to \{1,2,\ldots,|E|\}\) such that the induced mapping \(f_g: V \to {N}\), defined by \(f_g(v) = \sum\{g(u,v): (u, v) \in E(G)\} \), is injective and \(f_g(V) = \{a,a+d,\ldots,a+(|V|-1)d\}\). We deal with \((a, d)\)-antimagic labelings of the antiprisms.
Let \(s'(G)\) denote the Hall-condition index of a graph \(G\). Hilton and Johnson recently introduced this parameter and proved that \(\Delta(G) \leq s'(G) \leq \Delta(G) + 1\). A graph \(G\) is \(s’\)-Class 1 if \(s'(G) = \Delta(G)\) and is \(s’\)-Class 2 otherwise. A graph \(G\) is \(s’\)-critical if \(G\) is connected, \(s’\)-Class 2, and, for every edge \(e\), \(s'(G – e) < s'(G)\). We use the concept of the fractional chromatic index of a graph to classify \(s’\)-Class 2 in terms of overfull subgraphs, and similarly to classify \(s’\)-critical graphs. We apply these results to show that the following variation of the Overfull Conjecture is true;
A graph \(G\) is \(s’\)-Class 2 if and only if \(G\) contains an overfull subgraph \(H\) with \(\Delta(G) = \Delta(H)\).
We prove that if \(m\) be a positive integer and \(X\) is a totally ordered set, then there exists a function \(\phi: X \to \{1,\ldots,m\}\) such that, for every interval \(I\) in \(X\) and every positive integer \(r \leq |I|\), there exist elements \(x_1 < x_2 < \cdots < x_r\) of \(I\) such that \(\phi(x_{i+1}) \equiv \phi(x_{i}) + 1 \pmod{m}\) for \(i=1,\ldots,r-1\).
We prove that the complete graph \(K_v\) can be decomposed into cuboctahedra if and only if \(v \equiv 1 \text{ or } 33 \pmod{48}\).
In this paper, we present algorithms for locating the vertices in a tree of \(n\) vertices of positive edge-weighted tree and a positive vertex-weighted tree from which we broadcast multiple messages in a minimum cost. Their complexity is \(O(n^2 \log n)\). It improves a direct recursive approach which gives \(O(n^3)\). In the case where all the weights are equal to one, the complexity is \(O(n)\).
The affine resolvable \(2-(27,9,4)\) designs were classified by Lam and Tonchev \([9, 10]\). We use their construction of the designs to examine the ternary codes of the designs and show, using Magma [3], that each of the codes, apart from two, contains, amongst its constant weight-9 codewords, a copy of the ternary code of the affine geometry design of points and planes in \(AG_3(F_3)\). We also show how the ternary codes of the 68 designs and of their dual designs, together with properties of the automorphism groups of the designs, can be used to characterize the designs.
A perfect hash function for a subset \(X\) of \(\{0,1,\ldots,n-1\}\) is an injection \(h\) from \(X\) into the set \(\{0,1,\ldots,m-1\}\).
Perfect hash functions are useful for the compact storage and fast retrieval of frequently used objects. In this paper, we discuss some new practical algorithms for efficient construction of perfect hash functions, and we analyze their complexity and program size.
A Kuratowski-type approach for \([2,3]\)-graphs, i.e., hypergraphs whose edges have cardinality not more than \(3\), is presented, leading to a well-quasi-order in such a context, with a complete obstruction set of six forbidden hypergraphs to plane embedding.
We show that, for all primes \(p \equiv 1 \pmod{4}\), \(29 \leq p < 10,000\), \(p \neq 97, 193, 257, 449, 641, 769, 1153, 1409, 7681\), there exist \({Z}\)-cyclic triplewhist tournaments on \(p\) elements which are also Mendelsohn designs. We also show that such designs exist on \(v\) elements whenever \(v\) is a product of such primes \(p\).
An algorithm is presented in which a polynomial deck, \(\mathcal{P}D\), consisting of \(m\) polynomials of degree \(m-1\), is analysed to check whether it is the deck of characteristic polynomials of the one-vertex-deleted subgraphs of the line graph, \(H\), of a triangle-free graph, \(G\). We show that if two necessary conditions on \(\mathcal{P}D\), identified by counting the edges and triangles in \(H\), are satisfied, then one can construct potential triangle-free root graphs, \(G\), and by comparing the polynomial decks of the line graph of each with \(\mathcal{P}D\), identify the root graph.
Let \(\sigma_2(G) = \min\{d_G(u)+d_G(v) | u,v \in V(G), u,v \notin E(G)\}\) for a non-complete graph \(G\). An \([a, b]\)-factor of \(G\) is a spanning subgraph \(F\) with minimum degree \(\delta(F) \geq a\) and maximum degree \(\Delta(F) \leq b\).
In this note, we give a partially positive answer to a conjecture of M. Kano. We prove the following results:
Let \(G\) be a 2-edge-connected graph of order \(n\) and let \(k \geq 2\) be an integer. If \(\sigma_2(G) \geq {4n}/{(k +2)}\), then \(G\) has a 2-edge-connected \([2, k]\)-factor if \(k\) is even and a 2-edge-connected \([2, k + 1]\)-factor if \(k\) is odd.
Indeed, if \(k\) is odd, there exists a graph \(G\) which satisfies the same hypotheses and has no 2-edge-connected \([2, k]\)-factor.
Nevertheless, we have shown that if \(G\) is 2-connected with minimum degree \(\delta(G) \geq {2n}/{(k +2)}\), then \(G\) has a 2-edge-connected \([2, k]\)-factor.
The Ramsey numbers \(r(C_4,G)\) are determined for all graphs \(G\) of order six.
In a \(t-(v,k,\lambda)\) directed design, the blocks are ordered \(k\)-tuples and every ordered \(t\)-tuple of distinct points occurs in exactly \(\lambda\) blocks (as a subsequence). We show that a simple \(3-(v,4,2)\) directed design exists for all \(v\). This completes the proof that the necessary condition \(\lambda v\equiv 0 \pmod 2\) for the existence of a \(3-(v,4,\lambda)\) directed design is sufficient.
We give a conjecture for the total chromatic number \(\chi_T\) of all Steiner systems and show its relationship to the celebrated Erdős, Faber, Lovász conjecture. We show that our conjecture holds for projective planes, resolvable Steiner systems and cyclic Steiner systems by determining their total chromatic number.
We propose a number of problems about \(r\)-factorizations of complete graphs. By a completely novel method, we show that \(K_{2n+1}\) has a \(2\)-factorization in which all \(2\)-factors are non-isomorphic. We also consider \(r\)-factorizations of \(K_{rn+1}\) where \(r \geq 3\); we show that \(K_{rn+1}\) has an \(r\)-factorization in which the \(r\)-factors are all \(r\)-connected and the number of isomorphism classes in which the \(r\)-factors lie is either \(2\) or \(3\).
In this paper, we show the necessary and sufficient conditions for a complete graph on \(n\) vertices with a hole of size \(v\) (\(K_n \setminus K_v\)) to be decomposed into isomorphic copies of \(K_3\) with a pendant edge.
For given edges \(e_1, e_2 \in E(G)\), a spanning trail of \(G\) with \(e_1\) as the first edge and \(e_2\) as the last edge is called a spanning \((e_1, e_2)\)-trail. In this note, we consider best possible degree conditions to assure the existence of these trails for every pair of edges in a \(3\)-edge-connected graph \(G\).
In this paper, it is proved that an abelian \((351, 126, 45)\)-difference set only exists in the groups with exponent \(39\). This fills two missing entries in Lopez and Sanchez’s table with answer “no”. Furthermore, if a Spence difference set \(D\) has Character Divisibility Property, then \(D\) is one of the difference sets constructed by Spence.
In this paper we concentrate on those graphs which are \((a, d)\)-face antimagic, and we show that the graphs \(D_n\) from a special class of convex polytopes consisting of \(4\)-sided faces are \((6n + 3, 2)\)-face antimagic and \((4n + 4, 4)\)-face antimagic. It is worth a conjecture, we feel, that \(D_n\) are \((2n + 5, 6)\)-face antimagic.
Let \(\{G(n,k)\}\) be a family of graphs where \(G(n, k)\) is the graph obtained from \(K_n\), the complete graph on \(n\) vertices, by removing any set of \(k\) parallel edges. In this paper, the lower bound for the multiplicity of triangles in any \(2\)-edge coloring of the family of graphs \(\{G(n, k)\}\) is calculated and it is proved that this lower bound is sharp when \(n \geq 2k + 4\) by explicit coloring schemes in a recursive manner. For the cases \(n = 2k + 1, 2k + 2\), and \(2k + 3\), this lower bound is not sharp and the exact bound in these cases are also independently calculated by explicit constructions.
In this paper we introduce a new parameter related to the index of convergence of Boolean matrices — the generalized index. The parameter is motivated by memoryless communication systems. We obtain the values of this parameter for reducible, irreducible and symmetric matrices.
In this paper we extend the definition of pseudograceful graphs given by Frucht [3] to all graphs \(G\) with vertex set \(V(G)\) and edge set \(E(G)\) such that
\(|V(G)| \leq |E(G)| + 1\) and we prove that if \(G\) is a pseudograceful graph, then \(G \cup K_{m,n}\).is pseudograceful
for \(m,n \geq 2\) and \((m,n) \neq (2,2)\) and is graceful for \(m,n \geq 2\). This enables us to obtain several new families of graceful and disconnected graphs.
A graph \(G\) is \(Z_m\)-well-covered if \(|I| \equiv |J| \pmod{m}\), for all \(I\), \(J\) maximal independent sets in \(V(G)\). A graph \(G\) is a \(1-Z_m\)-well-covered graph if \(G\) is \(Z_m\)-well-covered and \(G\setminus\{v\}\) is \(Z_m\)-well-covered, \(\forall v \in V(G)\). A graph \(G\) is strongly \(Z_m\)-well-covered if \(G\) is a \(Z_m\)-well-covered graph and \(G\setminus\{e\}\) is \(Z_m\)-well-covered, \(\forall e \in E(G)\). Here we prove some results about \(1-Z_m\)-well-covered and strongly \(Z_m\)-well-covered graphs.
There are two types of quadrangles in a projective plane, Fano quadrangles, and non-Fano quadrangles. The number of quadrangles in some small projective planes is counted according to type, and an interesting configuration in the Hughes plane is displayed.
Let \(S = T \sim (\cup\{A : A \in \mathcal{A}\})\), where \(T\) is a simply connected orthogonal polygon and \(\mathcal{A}\) is a collection of \(n\) pairwise disjoint open rectangular regions contained in \(T\). Point \(x\) belongs to the staircase kernel of \(S\), Ker \(S\), if and only if \(x\) belongs to Ker \(T\) and neither the horizontal nor the vertical line through \(x\) meets any \(A\) in \(\mathcal{A}\). This produces a Krasnosel’skii-type theorem for \(S\) in terms of \(n\). However, an example shows that, independent of \(n\), no general Krasnosel’skii number exists for \(S\).
We show that the secants of an arc of size near to \({\sqrt{2q}}\) cover almost half plane; also, a random union of \(log_2 q\) arcs of this size is such that its secants cover the plane.
Generalized Steiner triple systems, \(GS(2,3,n,g)\) are used to construct maximum constant weight codes over an alphabet of size \(g+1\) with distance \(3\) and weight \(3\) in which each codeword has length \(n\). The existence of \(GS(2,3,n,g)\) has been solved for \(g = 2,3,4,5,6,9\). The necessary conditions for the existence of a \(GS(2,3,n,g)\) are \((n-1)g \equiv 0 \pmod{2}\), \(n(n-1)g \equiv 0 \pmod{6}\), and \(n \geq g+2\). In this paper, the existence of a \(GS(2,3,7,g)\) for any given \(g \geq 7\) is investigated. It is proved that if there exists a \(GS(2,3,n,g)\) for all \(n\), \(g+2 \leq n \leq 9g+158\), satisfying the two congruences, then the necessary conditions are also sufficient. As an application it is proved that the necessary conditions for the existence of a \(GS(2,3,n,g)\) are also sufficient for \(g = 7,8\).
The Ramsey numbers \(r(C_5,G)\) are determined for all graphs \(G\) of order six.
For a graph \(G\), let \(Var(G)\) denote the variance of the degree sequence of \(G\), let \(sq(G)\) denote the sum of the squares of the degrees of \(G\), and let \(t(G)\) denote the number of triangles in \(G\) and in its complement. The parameters are related by:
\(Var(G) = \frac{sq(G)}{n} – d^2\)
where \(d\) is the average degree of \(G\), and
\(t(G) = \binom{n}{3} + \frac{sq(G)}{2} – {m(n-1)}\)
Let \(Var(n)\) denote the maximum possible value of \(Var(G)\) where \(G\) has \(n\) vertices, and let \(sq(n,m)\) and \(t(n,m)\) denote the maximum possible values of \(sq(G)\) and \(t(G)\), respectively, where \(G\) has \(n\) vertices and \(m\) edges. We present a polynomial time algorithm which generates all the graphs with \(n\) vertices and \(m\) edges having \(sq(G) = sq(n,m)\) and \(t(G) = t(n,m)\). This extends a result of Olpp which determined \(t(n,m)\). We also determine \(Var(n)\) precisely for every \(n\), and show that
\[ Var(n) = \frac{q(q-1)^2}{n}(1-\frac{q}{n}) =\frac{27}{256}n^2=O(n)\]
where \(q = [\frac{3n}{4}] \),(if \(n \equiv 2 \pmod 4\) the rounding is up ) thereby improving upon previous results.
This paper defines a new graph invariant by considering the set of connected induced subgraphs of a graph and defining a polynomial whose coefficients are determined by this partially ordered set of subgraphs. We compute the polynomial for a variety of graphs and also determine the effects on the polynomial of various graph operations.
For two vertices \(u\) and \(v\) of a connected graph \(G\), the set \(H(u, v)\) consists of all those vertices lying on a \(u-v\) geodesic in \(G\). Given a set \(S\) of vertices of \(G\), the union of all sets \(H(u,v)\) for \(u,v \in S\) is denoted by \(H(S)\). A convex set \(S\) satisfies \(H(S) = S\). The convex hull \([S]\) is the smallest convex set containing \(S\). The hull number \(h(G)\) is the minimum cardinality among the subsets \(S\) of \(V(G)\) with \([S] = V(G)\). When \(H(S) = V(G)\), we call \(S\) a geodetic set. The minimum cardinality of a geodetic set is the geodetic number \(g(G)\). It is shown that every two integers \(a\) and \(b\) with \(2 \leq a \leq b\) are realizable as the hull and geodetic numbers, respectively, of some graph. For every nontrivial connected graph \(G\), we find that \(h(G) = h(G \times K_2)\). A graph \(F\) is a minimum hull subgraph if there exists a graph \(G\) containing \(F\) as induced subgraph such that \(V(F)\) is a minimum hull set for \(G\). Minimum hull subgraphs are characterized.
For a graph \(G = (V, E)\), a set \(S \subseteq V\) is a dominating set if every vertex in \(V – S\) is adjacent to at least one vertex in \(S\). A dominating set \(S \subseteq V\) is a paired-dominating set if the induced subgraph \(\langle S\rangle\) has a perfect matching. We introduce a variant of paired-domination where an additional restriction is placed on the induced subgraph \(\langle S\rangle \). A paired-dominating set \(S\) is an induced-paired dominating set if the edges of the matching are the induced edges of \(\langle S\rangle\), that is, \(\langle S\rangle\) is a set of independent edges. The minimum cardinality of an induced-paired dominating set of \(G\) is the induced-paired domination number \(\gamma_{ip}(G)\). Every graph without isolates has a paired-dominating set, but not all these graphs have an induced-paired dominating set. We show that the decision problem associated with induced-paired domination is NP-complete even when restricted to bipartite graphs and give bounds on \(\gamma_{ip}(G)\). A characterization of those triples \((a, b, c)\) of positive integers \(a \leq b \leq c\) for which a graph has domination number \(a\), paired-domination number \(b\), and induced-paired domination \(c\) is given. In addition, we characterize the cycles and trees that have induced-paired dominating sets.
Let \(M\) be an \(m\)-subset of \(\mathrm{PG}(k, 2)\), the finite projective geometry of dimension \(k\) over \(\mathrm{GF}(2)\). We would like to know the maximum number of lines that can be contained in \(M\). In this paper, we will not only give the maximum number of lines contained in \(m\)-subsets of \(\mathrm{PG}(k,2)\), but also construct an \(m\)-subset of \(\mathrm{PG}(k,2)\) containing the maximum number of lines.
Maximal partial spreads of the sizes \(13, 14, 15, \ldots, 22\) and \(26\) are described. They were found by using a computer. The computer also made a complete search for maximal partial spreads of size less than or equal to \(12\). No such maximal partial spreads were found.
Suppose we are given a set of sticks of various integer lengths, and that we have a knife that can cut as many as \(w\) sticks at a time. We wish to cut all the sticks up into pieces of unit length. By what procedure should the sticks be cut so that the total number of steps required is minimum? In this paper we show that the following natural algorithm is optimal: at each stage, choose the \(w\) longest sticks (or all sticks of length \(> 1\) if there are fewer than \(w\) of them) and cut them all in half (or as nearly in half as possible).
In this paper, we study intersection assignments of graphs using multiple intervals for each vertex, where each interval is of identical length or in which no interval is properly contained in another. The resulting parameters unit interval number, \(i_u(G)\) and proper interval number, \(i_p(G)\) are shown to be equal for any graph \(G\). Also, \(i_u(G)\) of a triangle-free graph \(G\) with maximum degree \(D\) is \(\left\lceil\frac{D+1}{2}\right\rceil\) if \(G\) is regular and \(\left\lceil\frac{D}{2}\right\rceil\) otherwise.
In [3] Brualdi and Hollingsworth conjectured that for any one-factorization \(\mathcal{F}\) of \(K_n\), there exists a decomposition of \(K_{2n}\) into spanning trees orthogonal to \(\mathcal{F}\). They also showed that two such spanning trees always existed. We construct three such trees and exhibit an infinite class of complete graphs with an orthogonal decomposition into spanning trees with respect to the one-factorization \(GK_{2n}\).
Four generalized theorems involving partitions and \((n+1)\)-color partitions are proved combinatorially. Each of these theorems gives us infinitely many partition identities. We obtain new generating functions for \(F\)-partitions and discuss some particular cases which provide elegant Rogers-Ramanujan type identities for \(F\)-partitions.
The aim of this paper is to study the isoperimetric numbers of double coverings of a complete graph. It turns out that these numbers are very closely related to the bisection widths of the double coverings and the degrees of unbalance of the signed graphs which derive the double coverings. For example, the bisection width of a double covering of a complete graph \(K_m\) is equal to \(m\) times its isoperimetric number. We determine which numbers can be the isoperimetric numbers of double coverings of a complete graph.
A digraph operation called pushing a set of vertices is studied with respect to tournaments. When a set \(X\) of vertices is pushed, the orientation of every arc with exactly one end in \(X\) is reversed. We discuss the problems of which tournaments can be made transitive and which can be made isomorphic to their converse using this operation.
Let \(I(G)\) be a graphical invariant defined for any graph \(G\). For several choices of \(I\) representing domination parameters, we characterize sequences of positive integers \(a_1,a_2,\ldots,a_n\) which have an associated sequence of graphs \(G_1,G_2,\ldots,G_n\) such that \(G_i\) has \(i\) vertices, \(G_i\) is an induced subgraph of \(G_{i+1}\), and \(I(G_i) = a_i\).
The fine structure of a directed triple system of index \(\lambda\) is the vector \((c_1,c_2,\ldots,c_\lambda)\), where \(c_i\) is the number of directed triples appearing precisely \(i\) times in the system. We determine necessary and sufficient conditions for a vector to be the fine structure of a directed triple system of index \(3\) for \(v \equiv 2 \pmod{3}\).
Gronau, Mullin and Pietsch determined the exact closure of index one of all subsets \(K\) of \(\{3,\ldots,10\}\) which include \(3\). We extend their results to obtain the exact closure of such \(K\) for all indices.
For every connected, even-degree graph \(G\) with \(10\) or fewer edges, the problem of finding necessary and sufficient conditions for the existence of a decomposition of \(K_v\) into edge-disjoint copies of \(G\) is completely settled.
The Huffman coding scheme is a character-based algorithm in which every leaf node represents a character only. In this paper, we study three variations of the Huffman coding scheme for compressing \(16\)-bit Chinese language. Although it is observed that \(IDC\) can generate the shortest code length among the three variations, but its empirical compression ratio is below \(1.8\), which is unsatisfactory. In order to achieve higher compression performance, i.e., compression ratio over \(2\), word-based compression algorithms should be employed. A possible way to develop word-based algorithms is to use the technique of cascading. Two kinds of algorithms are chosen for cascading. They are \(LZ\) algorithms and the Huffman coding scheme. \(LZ\) algorithms are used for finding repeating phrases while the Huffman coding scheme is used for encoding the phrases instead of characters. The experimental results show that the cascading algorithm of \(LZSSPDC\) outperforms a famous \(UNIX\) cascading compressor \(GZIP\) by \(5\%\) on average.
Grotzsch conjectured that if \(G\) is planar, bridgeless with \(\Delta = 3\) and \(n_2 \geq 2\), then \(G\) is of Class one. We prove that when \(n_2 = 2\) the conjecture is equivalent to the statement: \(G\) is \(3\)-critical if \(G\) is planar, bridgeless with \(\Delta = 3\) and \(n_2 = 1\). Then we prove that the conjecture implies the Four Color Theorem.
In this paper, we prove that a \(V(3, t)\) exists for any prime power \(3t + 1\), except when \(t = 5\), as no \(V(3, 5)\) exists.
In this paper, we survey some recent bounds on domination parameters. A characterisation of connected graphs with minimum degree at least 2 and domination number exceeding a third their size is obtained. Upper bounds on the total domination number, \(\gamma_t(G)\), of a graph \(G\) in terms of its order and size are established. If \(G\) is a connected graph of order \(n\) with minimum degree at least 2, then either \(\gamma_t(G) \leq 4n/7\) or \(G \in \{C_3,C_5,C_6,C_{10}\}\). A characterisation of those graphs of order \(n\) which are edge-minimal with respect to satisfying \(G\) connected, \(\delta(G) \geq 2\), and \(\gamma(G) \geq 4n/7\) is obtained. We establish that if \(G\) is a connected graph of size \(q\) with minimum degree at least 2, then \(\gamma_t(G) \leq (q + 2)/2\). Connected graphs \(G\) of size \(q\) with minimum degree at least 2 satisfying \(\gamma_t(G) > q/2\) are characterised. Upper bounds on other domination parameters, including the strong domination number and the restrained domination number are presented. We provide a constructive characterisation of those trees with equal domination and restrained domination numbers. A constructive characterisation of those trees with equal domination and weak domination numbers is also obtained.
Necessary and sufficient conditions for the existence of a decomposition of \(\lambda K_v\) into edge-disjoint copies of the Petersen graph are proved.
A \((v,k,t)\) trade \(T = T_1 – T_2\) of volume \(m\) consists of two disjoint collections \(T_1\) and \(T_2\), each containing \(m\) blocks (\(k\)-subsets) such that every \(t\)-subset is contained in the same number of blocks in \(T_1\) and \(T_2\). If each \(t\)-subset occurs at most once in \(T_1\), then \(T\) is called a Steiner \((k,t)\) trade. In this paper, the spectrum (that is, the set of allowable volumes) of Steiner trades is discussed, with particular reference to the case \(t = 2\). It is shown that the volume of a Steiner \((k, 2)\) trade is at least \(2k – 2\) and cannot equal \(2k – 1\). We show how to construct a Steiner \((k, 2)\) trade of volume \(m\) when \(m \geq 3k – 3\), or \(m\) is even and \(2k – 2 \leq m \leq 3k – 4\). For \(k = 5\) or \(6\), the non-existence of Steiner \((k,2)\) trades of volume \(2k + 1\) is demonstrated, and for \(k = 7\), we exhibit a Steiner \((k,2)\) trade of volume \(2k + 1\). In addition, the structure of Steiner \((k,2)\) trades of volumes \(2k – 2\) and \(2k\) (\(k \neq 3,4\)) is shown to be unique. A generalisation of our constructions to trades with blocks based on arbitrary simple graphs is also presented.
This paper characterizes a particular scheme of partially filled Latin squares and when they can be completed to full Latin squares. In particular, given an \(n \times n\) array with the first \(s\) rows and the first \(d\) cells of row \(s+1\) filled with \(n\) distinct symbols in such a way that no symbol occurs more than once in any row or column, necessary and sufficient conditions are found for when this array can be completed to a full Latin square.
We give counterexamples for two theorems given for the integrity of prisms and ladders in [2] (Theorem 2.17 and Theorem 2.18 in [1]). We also compute the integrity of several special graphs.
We apply a lattice point counting method due to Blass and Sagan [2] to compute the characteristic polynomials for the subspace arrangements interpolated between the Coxeter hyperplane arrangements. Our proofs provide combinatorial interpretations for the characteristic polynomials of such subspace arrangements. In the process of doing this, we explore some interesting properties of these polynomials.
A graph of a puzzle is obtained by associating each possible position with a vertex and by inserting edges between vertices if and only if the corresponding positions can be obtained from each other in one move. Computational methods for finding the vertices at maximum distance \(\delta\) from a vertex associated with a goal position are presented. Solutions are given for small sliding block puzzles, and methods for obtaining upper and lower bounds on \(\delta\) for large puzzles are considered. Old results are surveyed, and a new upper bound for the 24-puzzle is obtained: \(\delta \leq 210\).
The total domination number \(\gamma_t(G)\) of graph \(G = (V, E)\) is the cardinality of a smallest subset \(S\) of \(V\) such that every vertex of \(V\) has a neighbor in \(S\). It is known that, if \(G\) is a connected graph with \(n\) vertices, \(\gamma_t(G) \leq \left\lfloor{2n}/{3}\right\rfloor\). Graphs achieving this bound are characterized.
Until quite recently, very few weakly completable critical sets were known. The purpose of this note is to prove the existence of at least one Latin square of each order greater than four in which a weakly completable set exists. This is done by actual construction of such a square. Non-existence of weakly completable sets in Latin squares of orders 2, 3, and 4 is already known.
In our recent paper Necessary and sufficient conditions for some two variable orthogonal designs in order 44, Koukouvinos, Mitrouli and Seberry leave 7 cases unresolved. Using a new algorithm given in our paper A new algorithm for computer searches for orthogonal designs by the present four authors we are able to finally resolve all these cases.
This note records that the necessary conditions for the existence of two variable designs constructed using four circulant matrices are sufficient. In particular, of 484 potential cases, 404 cases have been found, 68 cases do not exist, and 12 cases cannot be constructed using four circulant matrices.
We determine the number of non-isomorphic triple systems with bipoints in those cases for which the total number of triples does not exceed 20.
Temporal load-balancing – “spreading out” the executions of tasks over time — is desirable in many applications. A form of temporal load-balancing is introduced: scheduling to maximize minimum inter-completion time (MICT-scheduling). It is shown that MICT-scheduling is, in general, NP-hard. A number of restricted classes of task systems are identified, which can be efficiently MICT-scheduled.
Given a finite-dimensional vector space \(V\) over a finite field \(F\) of odd characteristic, and equipping \(V\) with an orthogonal (symplectic, unitary) geometry, the following two questions are considered:
An exact answer to the first question is derived. Here there are two cases to consider, depending on whether or not the column vector \((\alpha_i)\) is in the column space of \(A\). This result can then be applied iteratively to address the second question.
Let \(G\) be a finite graph and let \(\mu\) be an eigenvalue of \(G\) of multiplicity \(k\). A star set for \(\mu\) may be characterized as a set \(X\) of \(k\) vertices of \(G\) such that \(\mu\) is not an eigenvalue of \(G – X\). It is shown that if \(G\) is regular then \(G\) is determined by \(\mu\) and \(G – X\) in some cases. The results include characterizations of the Clebsch graph and the Higman-Sims graph.
We show that if, for any fixed \(r\), the neighbourhood unions of all \(r\)-sets of vertices are large enough, then \(G\) will have many edge-disjoint perfect matchings. In particular, we show that given fixed positive integers \(r\) and \(c\) and a graph \(G\) of even order \(n\), if the minimum degree is at least \(r + c – 1\) and if the neighbourhood union of each \(r\)-set of vertices is at least \(n/2 + \left(2\lfloor\frac{(c + 1)}{2}\rfloor – 1\right)r\), then \(G\) has \(c\) edge-disjoint perfect matchings, for \(n\) large enough. This extends earlier work by Faudree, Gould and Lesniak on neighbourhood unions of pairs of vertices.
In this paper, necessary and sufficient conditions for a vector to be the fine structure of a balanced ternary design with block size \(3\), index \(3\) and \(\rho_2 = 1\) and \(2\) are determined, with one unresolved case.
Let \(K^d_n\) be the product of \(d\) copies of the complete graph \(K_4\). Wojciechowski [4] proved that for any \(d \geq 2\) the hypercube \(K^d_2\) can be vertex covered with at most \(16\) disjoint snakes. We show that for any odd integer \(n \geq 3\), \(d \geq 2\) the graph \(K^d_n\) can be vertex covered with \(2n^3\) snakes.
Cwatsets are subsets of \(\mathbb{Z}^d_2\) which are nearly subgroups and which naturally appear in statistics and coding theory [8]. Each cwatset can be represented by a highly symmetric hypergraph [7]. We introduce and study the symmetry group of the hypergraph and connect it to the corresponding cwatset. We use this connection to establish structure theorems for several classes of cwatsets.
Bollobás, Brightwell [1] and independently Shi [3] proved the existence of a cycle through all vertices of degree at least \(\frac{n}{2}\) in any \(2\)-connected graph of order \(n\). The aim of this paper is to show that the above degree requirement can be relaxed for \(1\)-tough graphs.
In this paper we investigate the \(k\)th lower multiexponent \(f(n,k)\) for tournament matrices.
It was proved that \(f(m,3) = 2\) if and only if \(m \geq 11\). Thus the conjecture in [2] is disproved. Further we obtain a new sufficient condition for \(f(n,k) = 1\).
The cycle graph \(C(H)\) of a graph \(H\) is the edge intersection graph of all induced chordless cycles of \(H\). We investigate iterates of the mapping \(\overline{C}: G \rightarrow C(\overline{G})\) where \(C\) denotes the map that associates to a graph its cycle graph. We call a graph \(G\) vanishing under \(\overline{C}\) if \(\overline{C^n}(G) = 0\) for some \(n\), otherwise \(G\) is called \(\overline{C}\)-persistent. We call a graph \(G\) expanding under \(\overline{C}\) if \(|\overline{C^n}(G)| \to \infty\) as \(n \to \infty\). We show that the lowest order of a \(\overline{C}\)-expanding graph is \(6\) and determine the behaviour under \(\overline{C}\) of some special graphs, including trees, null graphs, cycles and complete bipartite graphs.
Nonbinary power residue codes are constructed using the relationship between these codes and quasi-cyclic codes. Eleven of these codes exceed the known lower bounds on the maximum possible minimum distance of a linear code.
In this paper the authors study one- and two-dimensional color switching problems by applying methods ranging from linear algebra to parity arguments, invariants, and generating functions. The variety of techniques offers different advantages for addressing the existence and uniqueness of minimal solutions, their characterizations, and lower bounds on their lengths. Useful examples for reducing problems to easier ones and for choosing tools based on simplicity or generality are presented. A novel application of generating functions provides a unifying treatment of all aspects of the problems considered.
Broadcasting refers to the process of information dissemination in a communication network whereby a message is to be sent from a single originator to all members of the network, subject to the restriction that a member may participate in only one message transfer during a given time unit. In this paper we present a family of broadcasting schemes over the odd graphs, \(O_{n+1}\). It is shown that the broadcast time of \(O_{n+1}\), \(b(O_{n+1})\), is bounded by \(2n\). Moreover, the conjecture that \(b(O_{n+1}) = 2n\) is put forward, and several facts supporting this conjecture are given.
We derive a formula for the expected value \(\mu(2n+1)\) of the independent domination number of a random binary tree with \(2n+1\) vertices and determine the asymptotic behavior of \(\mu(2n+1)\) as \(n\) goes to infinity.
In [5], Gueizow gave an example of semiboolean SQS-skeins of nilpotent class \(2\), all its derived sloops are Boolean “or” of nilpotence class \(1\). In this paper, we give an example of nilpotent SQS-skein of class \(2\) whose derived sloops are all of nilpotence class \(2\). Guelzow [6] has also given a construction of semiboolean SQS-skeins of nilpotence class \(n\) whose derived sloops are all of class \(1\). As an extension result, we prove in the present paper the existence of nilpotent SQS-skeins of class \(n\) all of whose derived sloops are nilpotent of the same class \(n\); for any positive integer \(n\).
In this note we solve almost completely a problem raised by Topp and Volkmann [7] concerning the product of the domination and the chromatic numbers of a graph.
The concept of a strong \(a\)-valuation was introduced by Maheo, who showed that if a graph \(G\) has a strong \(a\)-valuation, then so does \(G \times K_2\). We show that for various graphs \(G\), \(G \times Q_n\) has a strong \(a\)-valuation and \(G \times P_n\) has an \(a\)-valuation, where \(Q_n\) is the \(n\)-cube and \(P_n\) the path with \(n\) edges, including \(G = K_{m,2}\) for any \(m\). Yet we show that \(K_{m,n} \times K_2\) does not have a strong \(a\)-valuation if \(m\) and \(n\) are distinct odd integers.
Let \(p\) be an odd prime number. We introduce a simple and useful decoding algorithm for orthogonal Latin square codes of order \(p\). Let \({H}\) be the parity check matrix of orthogonal Latin square code. For any \({x} \in {GF}(p)^n\), we call \(2 {H}^t\) the syndrome of \({x}\). This method is based on the syndrome-distribution decoding for linear codes. In \(\mathcal {L}_p\), we need to find the first and the second coordinates of codeword in order to correct the errored received vector.
The maximum cardinality of a partition of the vertex set of a graph \(G\) into dominating sets is the domatic number of \(G\), denoted \(d(G)\). We consider Nordhaus-Gaddum type results involving the domatic number of a graph, where a Nordhaus-Gaddum type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. Thereafter we investigate the upper bounds on the sum and product of the domatic numbers \(d(G_1), d(G_2)\) and \(d(G_3)\) where \(G_1 \oplus G_2 \oplus G_3 = K_n\). We show that the upper bound on the sum is \(n+2\), while the maximum value of the product is \(\lceil \frac{n}{3} \rceil ^3\) for \(n > 57\).
Place a checker in some square of an \(n \times n\) checkerboard. The checker is allowed to step either to the east or to the north, and is allowed to step off the edge of the board in a manner suggested by the usual identification of the edges of the square to form a projective plane. We give an explicit description of all the routes that can be taken by the checker to visit each square exactly once.
Bailey (1989) defined a \(k \times v\) double Youden rectangle (DYR), with \(k 3\) is a prime power with \(k \equiv 3 \pmod{4}\). We now provide a general construction for DYRs of sizes \(k \times (2k+1)\) where \(k > 5\) is a prime power with \(k \equiv 1 \pmod{4}\). We present DYRs of sizes \(9 \times 19\) and \(13 \times 27\).
We show by an elementary argument that, given any greedy clique decomposition of a graph \(G\) with \(n\) vertices, the sum of the orders of the cliques is less than \(\frac{5}{8}n^2\). This gives support to a conjecture of Peter Winkler.
We study the signed domination number \(\gamma_s\), the minus domination number \(\gamma^-\) and the majority domination number \(\gamma_{\mathrm{maj}}\). In this paper, we establish good lower bounds for \(\gamma_s\), \(\gamma^-\) and \(\gamma_{\mathrm{maj}}\), and give sharp lower bounds for \(\gamma_s\), \(\gamma^-\) for trees.
In this paper, nineteen new binary linear codes are presented which improve the bounds on the maximum possible minimum distance. These codes belong to the class of quasi-cyclic (QC) codes, and have been constructed using a stochastic optimization algorithm, tabu search. Six of the new codes meet the upper bound on minimum distance and so are optimal.
This game is a mixture of Searching and Cops and Robber. The Cops have partial information provided by sensing devices called photo radar. The Robber has perfect information. We give bounds on the number of photo radar units required by one Cop to capture a Robber on a tree and, with less tight bounds, on a copwin graph.
Cographs—complement-reducible graphs—can be viewed as intersection graphs (of \(k\)-dimensional boxes), as intersections of graphs (of \(P_4 ,C_4\)-free graphs), and as common tieset graphs of two-terminal graphs. This approach connects cographs with other topics such as chordal, interval, and series-parallel graphs, and it provides a natural dimension for cographs.
We consider reconstruction problems involving square-celled animals and other, similar, problems. Our main results, Corollary 3.2 and Theorem 3.3, give positive answers to the problems raised at the end of [4] by Harary and Manvel.
We present connections between \(T\)-colorings of graphs and regular vertex-coloring for distance graphs. Given a non-negative integral set \(T\) containing \(0\), a \(T\)-coloring of a simple graph assigns each vertex a non-negative integer (color) such that the difference of colors of adjacent vertices cannot fall in \(T\). Let \(\omega(T)\) be the minimum span of a \(T\)-coloring of an \(n\)-vertex complete graph. It is known that the asymptotic coloring efficiency of \(T\), \(R(T) = \lim_{n\to\infty} \frac{\omega(n)}{n}\), exists for any \(T\). Given a positive integral set \(D\), the distance graph \(G(\mathcal{Z}, D)\) has as vertex set all integers \(\mathbb{Z}\), and two vertices are adjacent if their difference is in \(D\). We prove that the chromatic number of \(G(\mathcal{Z}, D)\), denoted as \(\chi(\mathcal{Z}, D)\), is an upper bound of \(\lceil R(T) \rceil\), provided \(D=T \setminus \{0\}\). This connection is used in calculating \(\chi_a(m, k)\), chromatic number of \(G(\mathcal{Z},D)\) as \(D = \{1,2,3,\ldots,m\} \setminus \{k\}\), \(m > k\). Early results about \(\chi_\beta(m,k)\) were due to Eggleton, Erdos and Skilton [1985] who determined \(\chi_\beta(m,k)\) as \(k = 1\), partially settled the case \(k = 2\), and obtained upper and lower bounds for other cases. We show that \(\chi_\beta(m, k) = k\), if \(m < 2k\); and \(\chi_\beta(m,k) = \lceil \frac{m+k+1}{2} \rceil\), if \(m \geq 2k\) and \(k\) is odd. Furthermore, complete solutions for \(k = 2\) and \(4\), and partial solutions for other even numbers \(k\) are obtained. All the optimal proper colorings presented are periodic with smallest known periods.
The nonexistence of digraphs with order equal to the Moore bound \(\mathrm{M_{d,k}} = 1+d+\ldots+ d^h\) for \(d,k > 1\) has led to the study of the problem of the existence of “almost” Moore digraphs, namely digraphs with order close to the Moore bound. In [1], it was shown that almost Moore digraphs of order \(\mathrm{M_{d,k}} – 1\), degree \(d\), diameter \(k\) (\(d, k \geq 3\)) contain either no cycle of length \(k\) or exactly one such cycle. In this paper, we shall derive some further necessary conditions for the existence of almost Moore digraphs for degree \(d\) and diameter \(k \geq 1\). As a consequence, for diameter \(k = 2\) and degree \(d\), \(2 \leq d \leq 12\), we show that there are no almost Moore digraphs of order \(\mathrm{M_{d,2}} – 1\) with one vertex in a \(2\)-cycle \(C_2\) except the digraphs with every vertex in \(C_2\).
In this note we characterize the members of the Ramsey set \(\mathcal R(2K_2,tK_2)\) of all \((2K_2,tK_2)\)-minimal graphs using factor-critical graphs. Moreover, the sets \(\mathcal R(2K_2,tK_2)\) are determined for \(t \leq 5\).
Let \(G\) be a graph. A bijection \(f\) from \(V(G) \cup E(G)\) to \(\{1,2,\ldots,|V(G)| + |E(G)|\}\) is called a magic valuation if \(f(u)+f(v)+f(uv)\) is constant for any edge \(uv\) in \(G\). A magic valuation \(f\) of \(G\) is called a supermagic valuation if \(f(V(G)) = \{1,2,\ldots,|V(G)|\}\). The following theorem is proved.For any graph \(H\), there exists a connected graph \(G\) so that \(G\) contains \(H\) as an induced subgraph and \(G\) has a supermagic valuation.
For a graph \(G\), let \(\alpha(G)\) and \(\tau(G)\) denote the independence number of \(G\) and the matching number of \(G\), respectively. Further, let \(G \times H\) denote the direct product (also known as Kronecker product, cardinal product, tensor product, categorical product, and graph conjunction) of graphs \(G\) and \(H\). It is known that \(\alpha(G \times H) \geq \max\{\alpha(G)-|H|, \alpha(H)-|G|\} =: \underline{\alpha}(G \times H)\) and that \(\tau(G \times H) \geq 2.\tau(G).\tau(H) =: \underline{\tau}(G \times H)\). It is shown that an equality/inequality between \(\alpha\) and \(\underline{\alpha}\) is independent of an equality/inequality between \(\tau\) and \(\underline{\tau}\). Further, several results are presented on the existence of a complete matching in each of the two connected components of the direct product of two bipartite graphs. Additional results include an upper bound on \(\alpha(G \times H)\) that is achievable in certain cases.
All distinct double circulant self-dual codes over \(\text{GF}(5)\), with a minimum weight which is highest among all double circulant self-dual codes, have been found for each length \(n \leq 24\). For lengths \(14\), \(16\), and \(20\), these codes are extremal. In this paper, we characterize these extremal double circulant self-dual codes. In particular, a classification of extremal double circulant self-dual codes of length \(14\) is given. We present other double circulant codes which improve the lower bounds on the highest possible minimum weight. A classification of double circulant self-dual codes with parameters \([18, 9, 7]\) and \([24, 12, 9]\) is also given.
We modify the Knuth-Klingsberg Gray code for unrestricted integer compositions to obtain a Gray code for integer compositions each of whose parts is bounded between zero and some positive integer. We also generalize Ehrlich’s method for loop-free sequencing to implement this Gray code in \(O(1)\) worst-case time per composition. The \((n-1)\)-part compositions of \(r\) whose \(i\)th part is bounded by \(n-i\) are the inversion vectors of the permutations of \(\{1,\ldots,n\}\) with \(r\) inversions; we thus obtain a Gray code and a loop-free sequencing algorithm for this set of permutations.
The following problem was introduced at a conference in 1995. Fires start at \(F\) nodes of a graph and \(D\) defenders (firefighters) then protect \(D\) nodes not yet on fire. Then the fires spread to any neighbouring unprotected nodes. The fires and the firefighters take turns until the fires can no longer spread. We examine two cases: when the fires erupt at random and when they start at a set of nodes which allows the fires to maximize the damage. In the random situation, for a given number of nodes, we characterize the graphs which minimize the damage when \(D = F = 1\) and we show that the Star is an optimal graph for \(D = 1\) regardless of the value of \(F\). In the latter case, optimal graphs are given whenever \(D\) is at least as large as \(F\).
In this paper, we are concerned with the existence of sets of mutually quasi-orthogonal Latin squares (MQOLS). We establish a correspondence between equidistant permutation arrays and MQOLS, which has facilitated a computer search to identify all sets of MQOLS of order \(\leq 6\). In particular, we report that the maximum number of Latin squares of order 6 in a mutually quasi-orthogonal set is 3, and give an example of such a set. We also report on a non-exhaustive computer search for sets of 3 MQOLS of order 10, which, whilst not identifying such a set, has led to the identification of all the resolutions of each \((10, 3, 2)\)-balanced incomplete block design. Improvements are given on the existence results for MQOLS based on groups, and a new construction is given for sets of MQOLS based on groups from sets of mutually orthogonal Latin squares based on groups. We show that this construction yields sets of \(2^n – 1\) MQOLS of order \(2^n\), based on two infinite classes of groups. Finally, we give a new construction for difference matrices from mutually quasi-orthogonal quasi-orthomorphisms, and use this to construct a \((2^n, 2^n; 2)\)-difference matrix over \({C}_2^{n-2} \times {C}_4\).
For a countable bounded principal ideal poset \(P\) and a natural number \(r\), there exists a countable bounded principal ideal poset \(P’\) such that for an arbitrary \(r\)-colouring of the points (resp. two-chains) of \(P’\), a monochromatically embedded copy of \(P\) can be found in \(P’\). Moreover, a best possible upper bound for the height of \(P’\) in terms of \(r\) and the height of \(P\) is given.
A vertex set \(S \subseteq V(G)\) is a perfect code or efficient dominating set for a graph \(G\) if each vertex of \(G\) is dominated by \(S\) exactly once. Not every graph has an efficient dominating set, and the efficient domination number \(F(G)\) is the maximum number of vertices one can dominate given that no vertex is dominated more than once. That is, \(F(G)\) is the maximum influence of a packing \(S \subseteq V(G)\). In this paper, we begin the study of \(LF(G)\), the lower efficient domination number of \(G\), which is the minimum number of vertices dominated by a maximal packing. We show that the decision problem associated with deciding if \(LF(G) \leq K\) is an NP-complete problem. The principal result is a characterization of trees \(T\) where \(LF(T) = F(T)\).
We introduce a new class of colorings of graphs and define and study two new graph coloring parameters. A \({coloring}\) of a graph \(G = (V,E)\) is a partition \(\Pi = \{V_1, V_2, \ldots, V_k\}\) of the vertices of \(G\) into independent sets \(V_i\), or \({color\; classes}\). A vertex \(v_i \in V_i\) is called \({colorful}\) if it is adjacent to at least one vertex in every color class \(V_j\), \(i \neq j\). A \({fall \;coloring}\) is a coloring in which every vertex is colorful. If a graph \(G\) has a fall coloring, we define the \({fall\; chromatic\; number}\) (\({fall \;achromatic\; number}\)) of \(G\), denoted \(\chi_f(G)\), (\(\psi_f(G)\)) to equal the minimum (maximum) order of a fall coloring of \(G\), respectively. In this paper, we relate fall colorings to other colorings of graphs and to independent dominating sets in graphs.
This paper revises Park’s proof of Shannon inequality and also gives a new simple proof.
For \(\pi\) one of the upper domination parameters \(\beta\), \(\Gamma\), or \(IR\), we investigate graphs for which \(\pi\) decreases ( \(\pi\)-edge-critical graphs) and graphs for which \(\pi\) increases ( \(\pi^+\)-edge-critical graphs) whenever an edge is added. We find characterisations of \(\beta\)- and \(\Gamma\)-edge-critical graphs and show that a graph is \(IR\)-edge-critical if and only if it is \(\Gamma\)-edge-critical. We also exhibit a class of \(\Gamma^+\)-edge-critical graphs.
For a graph \(G = (V, E)\), a set \(S \subseteq V\) is a \(k\)-packing if the distance between every pair of distinct vertices in \(S\) is at least \(k+1\), and \(\rho_k(G)\) is the maximum cardinality of a \(k\)-packing. A set \(S \subseteq V\) is a distance-\(k\) dominating set if for each vertex \(u \in V – S\), the distance \(d(u, v) \leq k\) for some \(v \in S\). Call a vertex set \(S\) a \(k\)-independent dominating set if it is both a \(k\)-packing and a distance-\(k\) dominating set, and let the \(k\)-independent domination number \(i_k(G)\) be the minimum cardinality of a \(k\)-independent dominating set. We show that deciding if a graph \(G\) is not \(k\)-equipackable (that is, \(i_k(G) < \rho_k(G)\)) is an NP-complete problem, and we present a lower bound on \(i_k(G)\). Our main result shows that the sequence \((i_1(G), i_2(G), i_3(G), \ldots)\) is surprisingly not monotone. In fact, the difference \(i_{k+1}(G) – i_k(G)\) can be arbitrarily large.
Corresponding to chessboards, we introduce game boards with triangles or hexagons as cells and chess-like pieces for these boards. The independence number \(\beta\) is determined for many of these pieces.
We study the discrepancies of set systems whose incidence matrices are encoded by binary strings which are complex in the sense of Kolmogorov-Chaitin. We show that these systems display an optimal degree of irregularity of distribution.
We use the idea of compressibility to examine the discrepancy of set systems coded by complex sequences.
A multigraph is irregular if no two of its vertices have the same degree. It is known that every graph \(G\) with at most one trivial component and no component isomorphic to \(K_2\) is the underlying graph of some irregular multigraph. The irregularity cost of a graph with at most one trivial component and no component isomorphic to \(K_2\) is defined by \(ic(G) = \min\{|{E}(H)| – |{E}(G)| \mid H\) is an irregular multigraph containing G as underlying graph}. It is shown that if \(T\) is a tree on \(n\) vertices, then
\[\frac{n^2-3n+4}{4}\quad \leq \quad ic(T) \leq \binom{n-1}{2}\: \text{if}\: n\equiv0 \;\text{or}\; 3\pmod{4} \; \text{and}\]
\[\frac{n^2-3n+6}{4}\quad \leq \quad ic(T) \leq \binom{n-1}{2}\: \text{if}\: n\equiv1 \;\text{or}\; 2\pmod4 \]
Furthermore, these bounds are shown to be sharp.
The conjecture by E. Wojcicka, that every 3-domination-critical graph with minimum degree at least two is hamiltonian, has recently been proved in three different papers by five different authors. We survey the results which lead to the proof of the conjecture and consolidate them to form a unit.
The inflated graph \(G_1\) of a graph \(G\) is obtained by replacing every vertex of degree \(d\) by a clique \(K_d\). We pursue the investigation of domination related parameters of inflated graphs initialized by Dunbar and Haynes. They conjectured that the lower irredundance and domination parameters are equal for inflated graphs. Favaron showed that in general the difference between them can be as large as desired. In this article, we prove that the two parameters are equal for inflated trees.
This paper considers the following question: how many non-isomorphic proper edge-colourings (with any number of colours) are there of the complete graph \(K_n\)? We prove an asymptotic result and enumerate the solutions for \(n \leq 6\).
A directed network connecting a set \(A\) to a set \(B\) is a digraph containing an \(a\)-\(b\) path for each \(a \in A\) and \(b \in B\). Vertices in the directed network not in \(A \cup B\) are Steiner points. We show that in a finitely compact metric space in which geodesics exist, any two finite sets \(A\) and \(B\) are connected by a shortest directed network. We also bound the number of Steiner points by a function of the sizes of \(A\) and \(B\). Previously, such an existence result was known only for the Euclidean plane [M. Alfaro, Pacific J. Math. 167 (1995) 201-214]. The main difficulty is that, unlike the undirected case (Steiner minimal trees), the underlying graphs need not be acyclic.
Existence in the undirected case was first shown by E. J. Cockayne [Canad. Math. Bull. 10 (1967) 431-450].
A graph \(G\) is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), where the vertices in one class are colored red and those in the other class are colored blue. Let \(F\) be a 2-stratified graph rooted at some blue vertex \(v\). An \(F\)-coloring of a graph is a red-blue coloring of the vertices of \(G\) in which every blue vertex \(v\) belongs to a copy of \(F\) rooted at \(v\). The \(F\)-domination number \(\gamma_F(G)\) is the minimum number of red vertices in an \(F\)-coloring of \(G\). In this paper, we determine the \(F\)-domination number of the prisms \(C_n \times K_2\) for all 2-stratified claws \(F\) rooted at a blue vertex.
In this study, we consider the effect on the upper irredundance number \(IR(G)\) of a graph \(G\) when an edge is added joining a pair of non-adjacent vertices of \(G\). We say that \(G\) is \(IR\)-insensitive if \(IR(G + e) = IR(G)\) for every edge \(e \in \overline{E}\). We characterize \(IR\)-insensitive bipartite graphs and give a constructive characterization of graphs \(G\) for which the addition of any edge decreases \(IR(G)\). We also demonstrate the existence of a wide class of graphs \(G\) containing a pair of non-adjacent vertices \(u,v\) such that \(IR(G + uv) > IR(G)\).
A graph \(G\) is called \((a:b)\)-choosable if for every assignment of \(a\)-sets \(L(v)\) to the vertices of \(G\) it is possible to choose \(b\)-subsets \(M(v) \subseteq L(v)\) so that adjacent vertices get disjoint subsets. We give a different proof of a theorem of Tuza and Voigt that every \(2\)-choosable graph is \((2k:k)\)-choosable for any positive integer \(k\). Our proof is algorithmic and can be implemented to run in time \(O(k|V(G)|)\).
We prove some general results on irredundant sets of queens on chessboards, and determine the irredundance numbers of the queens graph \(Q_n\), for \(n = 5, 6\).
Let \(G\) be a graph. The weak domination number of \(G\), \(\gamma_w(G)\), is the minimum cardinality of a set \(D\) of vertices where every vertex \(u \notin D\) is adjacent to a vertex \(v \in D\), where \(\deg(v) \leq \deg(u)\). The strong domination number of \(G\), \(\gamma_s(G)\), is the minimum cardinality of a set \(D\) of vertices where every vertex \(u \notin D\) is adjacent to a vertex \(v \in D\), where \(\deg(v) \geq \deg(u)\). Similarly, the independent weak domination number, \(i_w(G)\), and the independent strong domination number, \(i_{st}(G)\), are defined with the additional requirement that the set \(D\) is independent. We find upper bounds on the number of edges of a graph in terms of the number of vertices and for each of these four domination parameters. We also characterize all graphs where equality is achieved in each of the four bounds.
For \(k \geq 2\), the \(P_k\)-free domination number \(\gamma(G; -P_k)\) is the minimum cardinality of a dominating set \(S\) in \(G\) such that the subgraph \(\langle S \rangle\) induced by \(S\) contains no path \(P_k\) on \(k\) vertices. The path-free domination number is at least the domination number and at most the independent domination number of the graph. We show that if \(G\) is a connected graph of order \(n \geq 2\), then \(\gamma(G; -P_k) \leq n + 2(k – 1) – 2\sqrt{n(k-1)}\), and this bound is sharp. We also give another bound on \(\gamma(G; -P_k)\) that yields the corollary: if \(G\) is a graph with \(\gamma(G) \geq 2\) that is \(K_{1,t+1}\)-free and \((K_{1,t+1}+e)\)-free (\(t \geq 3\)), then \(\gamma(G; -P_3) \leq (t-2)\gamma(G) – 2(t-3)\), and we characterize the extremal graphs for the corollary’s bound. Every graph \(G\) with maximum degree at most \(3\) is shown to have equal domination number and \(P_3\)-free domination number. We define a graph \(G\) to be \(P_k\)-domination perfect if \(\gamma(H) = \gamma(H; -P_k)\) for every induced subgraph \(H\) of \(G\). We show that a graph \(G\) is \(P_3\)-domination perfect if and only if \(\gamma(H) = \gamma(H; -P_3)\) for every induced subgraph \(H\) of \(G\) with \(\gamma(H) = 3\).
This paper is about critical sets in Latin squares and the weaker concept of partial Latin squares with unique completion. This work involves taking two known partial Latin squares with unique completion, or critical sets in Latin squares, and using a product construction to produce new partial Latin squares with unique completion, or new critical sets in larger Latin squares.
In this paper, we prove the following result:
Let \(D\) be a disconnected oriented graph of order \(n\). If
\(d^+(u)+d^+(v) \geq n-2\) for any pair \(u,v\) of nonadjacent vertices such that \(N^+(u) \cap N^+(v) \neq \emptyset\) and \(d^-(u) + d^-(v) \geq n-2\) for any pair \(u,v\) of nonadjacent vertices such that \(N^-(u) \cap N^-(v) \neq \emptyset\), then \(D\) contains a directed Hamiltonian cycle.
Let \(G\) be a graph. A vertex subversion strategy of \(G\), \(S\), is a set of vertices in \(G\) whose closed neighborhood is deleted from \(G\). The survival-subgraph is denoted by \(G/S\). The vertex-neighbor-integrity of \(G\), \(\mathrm{VNI}(G)\), is defined to be \(\mathrm{VNI}(G) = \min_{S\subseteq V(G)} \{|S| + w(G/S)\}\), where \(S\) is any vertex subversion strategy of \(G\), and \(w(G/S)\) is the maximum order of the components of \(G/S\). In this paper, we discuss the relationship between the vertex-neighbor-integrity and some well-known graphic parameters.
We construct, for all positive integers \(u\) and \(v\) with \(u \leq v\), a decomposition of \(K_v – K_u\) (the complete graph on \(v\) vertices with a hole of size \(u\)) into the maximum possible number of edge-disjoint triangles.
In this paper, we deal with the convex generators of a graph \(G = (V(G), E(G))\). A convex generator being a minimal set whose convex hull is \(V(G)\), we show that it is included in the “boundary” of \(G\). Then we show that the “boundary” of a polymino’s graph, or more precisely the seaweed’s “boundary”, enjoys some nice properties which permit us to prove that for such a graph \(G\), the minimal size of a convex generator is equal to the maximal number of hanging vertices of a tree \(T\), obtained from \(G\) by a sequence of generator-preserving contractions.
We address questions of Chartrand et al. about \(k\)-stratified graphs and distance graphs. A \(k\)-stratified graph \(G\) is a graph whose vertices have been partitioned into \(k\) distinct color classes, or strata. An underlying graph \(G’\) is obtained by ignoring the colors of \(G\). We prove that for every pair of positive integers \(k\) and \(l\), there exists a pair of \(2\)-stratified graphs with exactly \(k\) greatest common stratified subgraphs such that their underlying graphs have exactly \(l\) greatest common subgraphs.
A distance graph \(D(A)\) has vertices from some set \(A\) of \(0-1\) sequences of a fixed length and fixed weight. Two vertices are adjacent if one of the corresponding sequences can be obtained from the other by the interchange of a \(0\) and \(1\). If \(G\) is a graph of order \(m\) that can be realized as the distance graph of \(0-1\) sequences, then we prove that the \(0-1\) sequences require length at most \(2m-2\). We present a list of minimal forbidden induced subgraphs of distance graphs of \(0-1\) sequences.
A distance graph \(D(G)\) has vertices from some set \(G\) of graphs or \(k\)-stratified graphs. Two vertices are adjacent if one of the corresponding graphs can be obtained from the other by a single edge rotation. We prove that \(K_n\) minus an edge is a distance graph of a set of graphs. We fully characterize which radius one graphs are distance graphs of \(0-1\) sequences and which are distance graphs of graphs with distinctly labelled vertices.
The vertices of the queen’s graph \(Q_n\) are the squares of an \(n \times n\) chessboard and two squares are adjacent if a queen placed on one covers the other. Informally, a set \(I\) of queens on the board is irredundant if each queen in \(I\) covers a square (perhaps its own) which is not covered by any other queen in \(I\). It is shown that the cardinality of any irredundant set of vertices of \(Q_n\) is at most \(\left\lfloor {6n+6-8}\sqrt{n+3} \right\rfloor\) for \(n \geq 6\). We also show that the bound is not exact since \(\mathrm{IR}(Q_8) \leq 23\).
The star graph \(S_n\) is a graph with \(S_n\), the set of all permutations over \(\{1, \ldots, n\}\) as its vertex set; two vertices \(\pi_1\) and \(\pi_2\) are connected if \(\pi_1\) can be obtained from \(\pi_2\) by swapping the first element of \(\pi_2\) with one of the other \(n-1\) elements. In this paper we establish the genus of the star graph. We show that the genus, \(g_n\) of \(S_n\) is exactly equal to \(n!(n-4)/6+1\) by establishing a lower bound and inductively giving a drawing on a surface of appropriate genus.
In this note, a conjecture of P. Johnson Jr. on the Hall condition number is disproved.
Each vertex of a graph \(G = (V, E)\) is said to dominate every vertex in its closed neighborhood. A set \(S \subseteq V\) is a double dominating set for \(G\) if each vertex in \(V\) is dominated by at least two vertices in \(S\). The smallest cardinality of a double dominating set is called the double domination number \(dd(G)\). We initiate the study of double domination in graphs and present bounds and some exact values for \(dd(G)\). Also, relationships between \(dd(G)\) and other domination parameters are explored. Then we extend many results of double domination to multiple domination.
We investigate the following problem: given a set \(S \subset \mathbb{R}^2\) in general position and a positive integer \(k\), find a family of matchings \(\{M_1, M_2, \ldots, M_k\}\) determined by \(S\) such that if \(i \neq j\) then each segment in \(M_i\) crosses each segment in \(M_j\). We give improved linear lower bounds on the size of the matchings in such a family.
In this paper, we improve the upper bounds for the genus of the group \(\mathcal{A} = {Z}_{m_1} \times {Z}_{m_2} \times {Z}_{m_3}\) (in canonical form) with at least one even \(m_i\), \(i = 1, 2, 3\). As a special case, our results reproduce the known results in the cases \(m_3 = 3\) or both \(m_2\) and \(m_3\) are equal to \(3\).
Given a good drawing of a graph on some orientable surface, there exists a good drawing of the same graph with one more or one less crossing on an orientable surface which can be exactly determined. Our methods use a new combinatorial representation for drawings. These results lead to bounds related to the Thrackle Conjecture.
The minimum number of incomplete blocks required to cover, exactly \(\lambda\) times, all \(t\)-element subsets from a set \(V\) of cardinality \(v\) (\(v > t\)) is denoted by \(g(\lambda, t; v)\). The value of \(g(2, 2; v)\) is known for \(v = 3, 4, \ldots, 11\). It was previously known that \(13 \leq g(2, 2; 12) \leq 16\). We prove that \(g(2, 2; 12) \geq 14\).
In [8] a graph representation of the Fibonacci numbers \(F_n\) and Lucas numbers \(F_y^*\) was presented. It is interesting to know that they are the total numbers of all stable sets of undirected graphs \(P_n\) and \(C_n\), respectively. In this paper we discuss a more general concept of stable sets and kernels of graphs. Our aim is to determine the total numbers of all \(k\)-stable sets and \((k, k-1)\)-kernels of graphs \(P_n\) and \(C_n\). The results are given by the second-order linear recurrence relations containing generalized Fibonacci and Lucas numbers. Recent problems were investigated in [9], [10].
We give a constructive and very simple proof of a theorem by Chech and Colbourn [7] stating the existence of a cyclic \((4p, 4, 1)\)-BIBD (i.e. regular over \({Z}_{4p}\)) for any prime \(p \equiv 13 \mod 24\). We extend the theorem to primes \(p \equiv 1 \mod 24\) although in this case the construction is not explicit. Anyway, for all these primes \(p\), we explicitly construct a regular \((4p, 4, 1)\)-BIBD over \({Z}_{2}^{2} \oplus {Z}_p\).
In this paper, we prove the gracefulness of a new class of graphs denoted by \(K_{n}\otimes S_{2^{{n-1}}-\binom{n}{2}}\).
We also prove that the graphs consisting of \(2m + 1\) internally disjoint paths of length \(2r\) each, connecting two fixed vertices, are also graceful.
Erdős and Sésg conjectured in 1963 that if \(G\) is a graph of order \(p\) and size \(q\) with \(q > \frac{1}{2}p(k-1)\), then \(G\) contains every tree of size \(k\). This is proved in this paper when the girth of the complement of \(G\) is greater than \(4\).
Using path counting arguments, we prove
\(min\{\binom{x_1+x_2+y_1+y_2}{x_1,x_2,(y_1+y_2)},\binom{(x_1+x_2+y_1+y_2)}{(x_1+x_2),y_1,y_2}\}\leq\binom{x_1+y_1}{x_1}\binom{x_1+y_2}{x_1}\binom{x_2+y_1}{x_2}\binom{x_2+y_2}{x_2}\)
This inequality, motivated by graph coloring considerations, has an interesting geometric interpretation.
The existence of holey self-orthogonal Latin squares with symmetric orthogonal mates (HSOLSSOMs) of types \(h^n\) and \(1^{n}u^1\) is investigated. For type \(h^n\), new pairs of \((h, n)\) are constructed so that the possible exceptions of \((h, n)\) for the existence of such HSOLSSOMs are reduced to \(11\) in number. Two necessary conditions for the existence of HSOLSSOMs of type \(1^{n}u^1\) are (1) \(n \geq 3u + 1\) and (2) \(n\) must be even and \(u\) odd. Such an HSOLSSOM gives rise to an incomplete SOLSSOM. For \(3 \leq u \leq 15\), the necessary conditions are shown to be sufficient with seven possible exceptions. It is also proved that such an HSOLSSOM exists whenever even \(n \geq 5u + 9\) and odd \(u \leq 9\).
We prove: A connected magic graph with \(n\) vertices and \(q\) edges exists if and only if \(n = 2\) and \(q = 1\) or \(n \geq 5\) and \(\frac{5n}{4} < q < \frac{n(n-1)}{2} \).
Sharp bounds are presented for the \(\lambda\)-number of the Cartesian product of a cycle and a path, and of the Cartesian product of two cycles.
A set \(S = \{v_1, v_2, \ldots, v_n\}\) of vertices in a graph \(G\) with associated sequence \(k_1, k_2, \ldots, k_n\) of nonnegative integers is called a step domination set if every vertex of \(G\) is at distance \(k_i\) from \(v_i\) for exactly one \(i\) (\(1 \leq i \leq n\)). The minimum cardinality of a step domination set is called the step domination number of \(G\). This parameter is determined for several classes of graphs and is investigated for trees.
We completely determine the spectrum (i.e. set of orders) of complete \(4\)-partite graphs with at most one odd part which are decomposable into two isomorphic factors with a finite diameter. For complete \(4\)-partite graphs with all parts odd we solve the spectrum problem completely for factors with diameter \(5\). As regards the remaining possible finite diameters, \(2, 3, 4\), we present partial results, focusing on decompositions of \(K_{n,n,n,m}\) and \(K_{n,n,m,m}\) for odd \(m\) and \(n\).
In this paper we determine the \(k\)-domination numbers of the cardinal products \(P_2 \times P_n, \ldots, P_{2k+1} \times P_n\) for all integers \(k \geq 2, n \geq 3\).
In this paper we investigate the nature of both the \(2\)-packing number and the minimum domination number of the cartesian product of graphs where at least one of them has the property that every vertex is either a leaf or has at least one leaf as a neighbour.
Let \(H\) be a graph, and let \(k\) be a positive integer. A graph \(G\) is \(H\)-coverable with overlap \(k\) if there is a covering of all the edges of \(G\) by copies of \(H\) such that no edge of \(G\) is covered more than \(k\) times. The number \(ol(H, G)\) is the minimum \(k\) for which \(G\) is \(H\)-coverable with overlap \(k\).
It is established (Theorem 2.1) that if \(n\) is sufficiently large then
\[ol(H, K_n) \leq 2.\]
For \(H\) being a path, a matching or a star it is enough to assume \(|H| \leq n\) (Theorem 3.1).
The same result is obtained (Main Theorem) for any graph \(H\) having at most four vertices, or else at most four edges with a single exception \(ol(K_4, K_5) = 3\).
In this paper, we show that group divisible designs with block size five, group-type and index odd exist with a few possible exceptions.
A digraph \(D\) is called semicomplete \(c\)-partite if its vertex set \(V(D)\) can be partitioned into \(c\) sets (partite sets) such that for any two vertices \(x\) and \(y\) in different partite sets, at least one arc between \(x\) and \(y\) is in \(D\) and there are no arcs between vertices in the same partite set. The path covering number of \(D\) is the minimum number of paths in \(D\) that are pairwise vertex disjoint and cover the vertices of \(D\). Volkmann (1996) has proved two sufficient conditions on hamiltonian paths in semicomplete multipartite digraphs and conjectured two related sufficient conditions. In this paper, we derive sufficient conditions for a semicomplete multipartite digraph to have path covering number at most \(k\) and show that Volkmann’s results and conjectures can be readily obtained from our conditions.
The Fibonacci number of a graph is the number of independent sets of the graph. In this paper, we compute algorithmically the Fibonacci numbers of lattice product graphs.
In this note, we solve a conjecture of Dénes, Mullen, and Suchower [2] on power sets of Latin squares.
In this article, we construct a large set of idempotent quasigroups of order 62. The spectrum for large sets of idempotent quasigroups of order \(n\) (briefly, \(LQ(n)\)) is the set of all integers \(n \geq 3\) with the exception \(n = 6\) and the possible exception \(n = 14\).
We settle the existence status of some previously open cases of abelian difference sets. Our results fill ten missing entries in the recent table of Lepez and Sanchez, all with answer `No’.
Recently, Raines and Rodger have proved that for all \(\lambda \geq 1\), any partial extended triple system of order \(n\) and index \(\lambda\) can be embedded in a (complete) extended triple system of order \(v\) and index \(\lambda\) for any even \(v \geq 4n + 6\). In this note, it is shown that if \(\lambda\) is even then this bound on \(v\) can be improved to all \(v \geq 3n + 5\), and under some conditions to all \(v \geq 2n + 1\).
It is shown that if a graph \(G\) is connected, claw-free, and such that the vertices of degree 1 of every induced bull have a common neighbor in \(G\), then \(G\) is traceable.
Some extremal set problems can be phrased as follows. Given an \(m \times n\) \((0,1)\)-matrix \(A\) with no repeated columns and with no submatrix of a certain type, what is a bound on \(n\) in terms of \(m\)? We examine a conjecture of Frankl, Füredi, and Pach and the author that when we forbid a \(k \times l\) submatrix \(F\) then \(n\) is \(O(m^{k})\). Two proof techniques are presented, one is amortized complexity and the other uses a result of Alon to show that \(n\) is \(O(m^{2k-1-\epsilon})\) for \(\epsilon=(k-1)/(13 \log_2 l)\), improving on the previous bound of \(O(m^{2k-1})\).
A graph \(H\) is \(G\)-decomposable if \(H\) can be decomposed into subgraphs, each of which is isomorphic to \(G\). A graph \(G\) is a greatest common divisor of two graphs \(G_1\) and \(G_2\) if \(G \) is a graph of maximum size such that both \(G_1\) and \(G_2\) are \(G\)-decomposable. The greatest common divisor index of a graph \(G\) of size \(q\) is the greatest positive integer \(n\) for which there exist graphs \(G_1\) and \(G_2\), both of size at least \(nq\), such that \(G\) is the unique greatest common divisor of \(G_1\) and \(G_2\). The corresponding concepts are defined for digraphs. Relationships between greatest common divisor index for a digraph and for its underlying graph are studied. Several digraphs are shown to have infinite index, including matchings, short paths, union of stars, transitive tournaments, the oriented 4-cycle. It is shown that for \(5 \leq p \leq 10\), if a graph \(F\) of sufficiently large size is \(C_p\)-decomposable, then \(F\) is also \((P_{p-1} \cup P_3)\)-decomposable. From this it follows that the even cycles \(C_6\), \(C_8\) and \(C_{10}\) have finite greatest common divisor index.
A chess-like game board called a hive, consisting of hexagonal cells, and a board piece called a queen are defined. For queens on hexagonally shaped hives, values are obtained for the lower and independent domination numbers, the upper independence number and the diagonal domination number, as well as a lower bound for the upper domination number. The concept of a double column placement is introduced.
Two vertices in a graph \(H\) are said to be pseudosimilar if \(H – u\) and \(H – v\) are isomorphic but no automorphism of \(H\) maps \(u\) into \(v\). Pseudosimilar edges are analogously defined. Graphs in which every vertex is pseudosimilar to some other vertex have been known to exist since 1981. Producing graphs in which every edge is pseudosimilar to some other edge proved to be more difficult. We here look at two constructions of such graphs, one from \(\frac{1}{2}\)-transitive graphs and another from edge-transitive but not vertex-transitive graphs. Some related questions on Cayley line-graphs are also discussed.
The maximum cardinality of a partition of the vertex set of a graph \(G\) into dominating sets is the domatic number of \(G\), denoted \(d(G)\). The codomatic number of \(G\) is the domatic number of its complement, written \({d}(\overline{G})\). We show that the codomatic number for any cubic graph \(G\) of order \(n\) is \(n/2\), unless \(G \in \{K_4, G_1\}\) where \(G_1\) is obtained from \(K_{2,3} \cup K_3\) by adding the edges of a 1-factor between \(K_3\) and the larger partite set of \(K_{2,3}\).
Various connections have been established between the permanent and the determinant of the adjacency matrix of a graph. Connections are also made between these scalars and the number of perfect matchings in a graph. We establish conditions for graphs to have determinant 0 or \(\pm1\). Necessary conditions and sufficient conditions are obtained for graphs to have permanent equal to 0 or to 1.
Let \(h \geq 1\). For each admissible \(v\), we exhibit a nested balanced path design \(H(v, 2h+1, 1)\). For each admissible odd \(v\), we exhibit a nested balanced path design \(H(v,2h,1)\). For every \(v \equiv 4 \pmod{6}\), \(v \geq 10\), we exhibit a nested balanced path design \(H(v,4,1)\) except possibly if \(v \in \{16, 52, 70\}\).
For each \(v \equiv 0 \pmod{4h}\), \(v \geq 4h\), we exhibit a nested path design \(P(v,2h+1,1)\). For each \(v \equiv 0 \pmod{4h-2}\), \(v \geq 4h-2\), we exhibit a nested path design \(P(v,2h,1)\). For every \(v \equiv 3 \pmod{6}\), \(v \geq 9\), we exhibit a nested path design \(P(v,4,1)\) except possibly if \(v = 39\).
A sequence of positive integers \(a_1 \leq a_2 \leq \ldots \leq a_n\) is called an ascending monotone wave of length \(n\), if \(a_{i+1} – a_{i} \geq a_{i} – a_{i-1}\) for \(i = 2, \ldots, n-1\). If \(a_{i+1} – a_{i} > a_{i} – a_{i-1}\) for all \(i = 2, \ldots, n-1\) the sequence is called an ascending strong monotone wave of length \(n\). Let \({Z}_k\) denote the cyclic group of order \(k\). If \(k | n\), then we define \(MW(n, {Z}_k)\) as the least integer \(m\) such that for any coloring \(f : \{1, \ldots, m\} \to {Z}_k\), there exists an ascending monotone wave of length \(n\), where \(a_n \leq m\), such that \(\sum_{i=1}^n f(a_i) = 0 \mod k\). Similarly, define \(SMW(n, {Z}_k)\), where the ascending monotone wave in \(MW(n, {Z}_k)\) is replaced by an ascending strong monotone wave. The main results of this paper are:
These results are the zero-sum analogs of theorems proved in [1] and [5].
For \(\omega \leq 33\), the known necessary conditions for existence of a \((\nu,\{5,\omega^*\},1)\) PBD, namely \(\nu, \omega \equiv 1 \mod 4\), \(\nu \geq 4\omega+1\) and \(\nu \equiv \omega\) or \(4\omega +1 \mod 20\) are known to be sufficient in all but 26 cases. This paper provides several direct constructions which reduce the number of exceptions to 8.
The question whether every connected graph \(G\) has a spanning tree \(T\) of minimum average distance such that \(T\) is distance preserving from some vertex is answered in the negative. Moreover, it is shown that, if such a tree exists, it is not necessarily distance preserving from a median vertex.
In this note, we investigate three versions of the overfull property for graphs and their relation to the edge-coloring problem. Each of these properties implies that the graph cannot be edge-colored with \(\Delta\) colors, where \(\Delta\) is the maximum degree. The three versions are not equivalent for general graphs. However, we show that some equivalences hold for the classes of indifference graphs, split graphs, and complete multipartite graphs.
Let \(K_n\) be the complete graph on \(n\) vertices. Let \(I(X)\) denote the set of integers \(k\) for which a pair of maximum pentagon packings of graph \(X\) exist having \(k\) common 5-cycles. Let \(J(n)\) denote the set \(\{0,1,2,\ldots,P-2,P\}\), where \(P\) is the number of 5-cycles in a maximum pentagon packing of \(K_n\). This paper shows that \(I(K_n) = J(n)\), for all \(n \geq 1\).
It is shown that the Overfull Conjecture, which would provide a chromatic index characterization for a large class of graphs, and the Conformability Conjecture, which would provide a total chromatic number characterization for a large class of graphs, both in fact apply to almost all graphs, whether labelled or unlabelled. The arguments are based on Polya’s theorem, and are elementary in the sense that practically no knowledge of random graph theory is presupposed. It is similarly shown that the Biconformability Conjecture, which would provide a total chromatic number characterization for a large class of equibipartite graphs, in fact applies to almost all equibipartite graphs.
The \([0,\infty)\)-valued dominating function minimization problem has the \([0,\infty)\)-valued packing function as its linear programming dual. The standard \(\{0, 1\}\)-valued minimum dominating set problem has the \(\{0, 1\}\)-valued maximum packing set problem as its binary dual. The recently introduced complementary problem to a minimization problem is also a maximization problem, and the complementary problem to domination is the maximum enclaveless problem. This paper investigates the dual of the enclaveless problem, namely, the domination-coverage number of a graph. Specifically, let \(\eta(G)\) denote the minimum total coverage of a dominating set. The number of edges covered by a vertex \(v\) equals its degree, \(\deg v\), so \(\eta(G) = \text{MIN}\{\sum_{s \in S} \deg s: S \text{ is a dominating set}\}\). Bounds on \(\eta(G)\) and computational complexity results are presented.
In this note, we computationally prove that the size of smallest critical sets for the quaternion group of order eight, the group \(\mathbb{Z}_2 \times \mathbb{Z}_4\) and the dihedral group of order eight are 20, 21 and 22, respectively.
A graph is said \(h\)-decomposable if its edge-set is decomposable into hamiltonian cycles. In this paper, we prove that if \(G = L_1 \cup L_2 \cup L_3\) is a strongly hamiltonian bipartite cubic graph (where \(L_i\) is a perfect matching, for \(1 \leq i \leq 3\) and \((L_1, L_2, L_3)\) is a \(1\)-factorization of \(G\)), then \(G \times C_{2n+1}\) (where \(n\) is odd and \(n \geq 1\)) is decomposable. As a corollary, we show that for \(r \geq 1\) odd and \(n \geq 3\), \(K_{r,r} \times K_n\) is \(h\)-decomposable. Moreover, in the case where \(G\) is a strongly hamiltonian non-bipartite cubic graph, we prove that the same result can be derived using a special perfect matching. Hence \(K_{2r} \times K_{2n+1}\) will be \(h\)-decomposable, for \(r,n \geq 1\).
To study the product of \(G = L_1 \cup L_2 \cup L_3\) by even cycle, we define a dual graph \(G_C\) based on an alternating cycle subset of \(L_2 \cup L_3\). We show that if a non-bipartite cubic graph \(G = L_1 \cup L_2 \cup L_3\), with \(|V(G)| = 2m\), admits \(L_1 \cup L_2\) as a hamiltonian cycle and \(G_C\) is connected, then \(G \times K_2\) is hamiltonian and \(G \times C_{2n}\) has two edge-disjoint hamiltonian cycles. Finally, we prove that if \(C = L_2 \cup L_3\) and \(L_1 \cup L_3\) admits a particular alternating \(4\)-cycle \(C’\), then \(G \times C_{2n}\) is \(h\)-decomposable.
Given a digraph (an undirected graph, resp.) \(D\) and two positive integers \(f(x), g(x)\) for every \(x \in V(D)\), a subgraph \(H\) of \(D\) is called a \((g, f)\)-factor if \(g(x) \leq d^+_H(x) = d^-_H(x) \leq f(x)\) (\(g(x) \leq d_H(x) \leq f(x)\), resp.) for every \(x \in V(D)\). If \(f(x) = g(x) = 1\) for every \(x\), then a connected \((g, f)\)-factor is a hamiltonian cycle. The previous research related to the topic has been carried out either for \((g, f)\)-factors (in general, disconnected) or for hamiltonian cycles separately, even though numerous similarities between them have been recently detected. Here we consider connected \((g, f)\)-factors in digraphs and show that several results on hamiltonian digraphs, which are generalizations of tournaments, can be extended to connected \((g, f)\)-factors. Applications of these results to supereulerian digraphs are also obtained.
