In this paper, we construct two series of balanced incomplete block (BIB) designs with parameters:
\[v = \binom{2m-3}{2} ,r= \frac{(2m-5)!}{(m-1)!}, k= {m}\]
\[b=\frac{(2m-3)!}{2m(m-1)!} , \lambda = \frac{(2m-6)!}{(m-3)!}\]
and
\[v = \binom{2m+1}{2} , b = b_1(m+1), r = 2m(\overline{\lambda}_1-\overline{\lambda}_2), k = m^2\]
\[\lambda = (m-1)(\overline{\lambda}_1-2\overline{\lambda}_2+\overline{\lambda}_3)+m(\overline{\lambda}_2-\overline{\lambda}_3)\]
where \(k_1, b_1, \overline{\lambda}_i\) are parameters of a special \(4-(v, k, \lambda)\) design.
The strong chromatic index of a graph \(G\), denoted \(sq(G)\), is the minimum number of parts needed to partition the edges of \(G\) into induced matchings. The subset graph \(B_m(k)\) is the bipartite graph whose vertices represent the elements and the \(k\)-subsets of an \(m\) element ground set where two vertices are adjacent if and only if the vertices are distinct and the element corresponding to one vertex is contained in the subset corresponding to the other. We show that \(sq(B_m(k)) =\binom{m}{k-1}\) and that this satisfies the strong chromatic index conjecture by Brualdi and Quinn \([3]\) for bipartite graphs.
For a graph \(G\), if \(F\) is a nonempty subset of the edge set \(E(G)\), then the subgraph of \(G\) whose vertex set is the set of ends of edges in \(F\) is denoted by \(_G\). Let \(E(G) = \cup_{i \in I} E_i\) be a partition of \(E(G)\), let \(D_i = _G\) for each \(i\), and let \(\phi = (D_i | i \in I)\), then \(\phi\) is called a partition of \(G\) and \(E_i\) (or \(D_i\)) is an element of \(\phi\). Given a partition \(\phi = (D_i | i \in I)\) of \(G\), \(\phi\) is an admissible partition of \(G\) if for any vertex \(v \in V(G)\), there is a unique element \(D_i\) that contains vertex \(v\) as an inner point. For two distinct vertices \(u\) and \(v\), a \(u-v\) walk of \(G\) is a finite, alternating sequence \(u = u_0, e_1, u_1, e_2, \ldots, v_{n.1},e_n,u_n = v\) of vertices and edges, beginning with vertex \(u\) and ending with vertex \(v\), such that \(e_i = u_{i-1}u_i\) for \(i = 1, 2, \ldots, n\). A \(u-v\) string is a \(u-v\) walk such that no vertex is repeated except possibly \(u\) and \(v\), i.e., \(u\) and \(v\) are allowed to appear at most two times. Given an admissible partition \(\phi\), \(\phi\) is a string decomposition or \(SD\) of \(G\) if every element of \(\phi\) is a string.
In this paper, we prove that a \(2\)-connected graph \(G\) has an \(SD\) if and only if \(G\) is not a cycle. We also give a characterization of the graphs with cut vertices such that each graph has an \(SD\).
The cyclic chromatic number is the smallest number of colours needed to colour the nodes of a tournament so that no cyclic triple is monochromatic. Bagga, Beineke, and Harary \({[1]}\) conjectured that every tournament score vector belongs to a tournament with cyclic chromatic number \(1\) or \(2\). In this paper, we prove this conjecture and derive some other results.
A path of a graph is maximal if it is not a proper subpath of any other path of the graph. The path spectrum is the set of lengths of all maximal paths in the graph. A graph is scenic if its path spectrum is a singleton set. In this paper, we give a new proof characterizing all scenic graphs with a Hamiltonian path; this result was first proven by Thomassen in \(1974\). The proof strategy used here is also applied in a companion paper in which we characterize scenic graphs with no Hamiltonian path.
In this paper, we count \(n\)-block BTD\((V, B, R, 3, 2)\) configurations for \(n = 1\) and \(2\). In particular, we list all configuration types and determine formulae for the number of \(n\)-block subsets of a design of each type. A small number of the formulae are shown to be dependent solely on the design parameters. The remainder are shown to be dependent on the number of occurrences of two particular two-block configurations as well as the design parameters. Three new non-isomorphic BTD\((9; 33; 5, 3, 11; 3; 2)\) are given that illustrate the independence of certain configurations.
Sampathkumar and Pushpa Latha (see \({[3]}\)) conjectured that the independent domination number, \(i(T)\), of a tree \(T\) is less than or equal to its weak domination number, \(\gamma_w(T)\). We show that this conjecture is true, prove that \(\gamma_w(T) \leq \beta(T)\) for a tree \(T\), exhibit an infinite class of trees in which the differences \( \gamma_w-i \) and \(\beta – \gamma_w\) can be made arbitrarily large, and show that the decision problem corresponding to the computation of \(\gamma(G)\) is \(NP\)-complete, even for bipartite graphs. Lastly, we provide a linear algorithm to compute \(\gamma_w(T)\) for a tree \(T\).
We give operations on graphs preserving the property of being a \((0,2)\)-graph. In particular, these operations allow the construction of non-vertex-transitive \((0,2)\)-graphs. We also construct a family of regular interval-regular graphs which are not interval monotone, thus disproving a weaker version of a conjecture proposed by H.M. Mulder.
This paper investigates the number of spanning subgraphs of the product of an arbitrary graph \(G\) with the path graphs \(P_n\) on \(n\) vertices that meet certain properties: connectivity, acyclicity, Hamiltonicity, and restrictions on degree. A general method is presented for constructing a recurrence equation \(R(n)\) for the graphs \(G \times P_n\), giving the number of spanning subgraphs that satisfy a given combination of the properties. The primary result is that all constructed recurrence equations are homogeneous linear recurrence equations with integer coefficients. A second result is that the property “having a spanning tree with degree restricted to \(1\) and \(3\)” is a comparatively strong property, just like the property “having a Hamilton cycle”, which has been studied extensively in literature.
Broersma and Hoede studied the \(P_3\)-transformation of graphs and claimed that it is an open problem to characterize all pairs of nonisomorphic connected graphs with isomorphic connected \(P_3\)-graphs. In this paper, we solve the problem to a great extent by proving that the \(P_3\)-transformation is one-to-one on all graphs with minimum degree greater than two. The only cases that remain open are cases where some degree is 1 or 2, and examples indicate that the problem seems to be difficult in these cases. This in some sense can be viewed as a counterpart with respect to \(P_3\)-graphs for Whitney’s result on line graphs.
A graph \(H\) is called a seed graph if there exists a graph \(G\) such that the deletion of any closed neighborhood of \(G\) always results in \(H\). In this paper, we investigate disconnected seed graphs. By degree and order considerations, we show that for certain pairs of connected graphs, \(H_1\) and \(H_2\), \(H_1 \cup H_2\) cannot be a seed graph. Furthermore, for every connected graph \(H\) such that \(K_1 \cup H\) is a seed graph, we show that \(H\) can be obtained by a certain graph product of \(K_2\) and \(H’\), where \(H’\) is itself a seed graph.
The following problem is formulated:
Let \(P(G)\) be a graph parameter and let \(k\) and \(\delta\) be integers such that \(k > \ell \geq 0\). Suppose \(|G| = n\) and for any two \(k\)-subsets \(A, B \subset V(G)\) such that \(|A \cap B| = \ell\) it follows that \(P(\langle A\rangle) = P(\langle B\rangle )\). Characterize \(G\).
We solve this problem for two parameters, the domination number and the number of edges modulo \(m\) (for any \(m \geq \ell\)). These solutions extend and are based on an earlier work that dated back to a 1960 theorem of Kelly and Merriell.
A graph \(G\) is outer-projective-planar if it can be embedded in the projective plane so that every vertex appears on the boundary of a single face. We exhibit obstruction sets for outer-projective-planar graphs with respect to the subdivision, minor, and \(Y\Delta\) orderings. Equivalently, we find the minimal non-outer-projective-planar graphs under these orderings.
We establish an improved bound for the Union-Closed Sets Conjecture.
We show that for each fixed \(k \geq 3\), the \({INDEPENDENT \; SET}\) problem is \(NP\)-complete for the class of \(k\)-regular graphs. Several other decision problems, including \({IRREDUNDANT \; SET}\), are also \(NP\)-complete for each class of \(k\)-regular graphs, for \(k \geq 6\).
For a positive integer \(d\), the usual \(d\)-dimensional cube \(Q_d\) is defined to be the graph \((K_2)^d\), the Cartesian product of \(d\) copies of \(K_2\). We define the generalized cube \(Q_{d,k}\) to be the graph \((K_k)^d\) for positive integers \(d\) and \(k\). We investigate the decompositions of the complete graph \(K_{k^d}\) and the complete \(k\)-partite graph \(K_{k \times k^{d-1}}\) into generalized cubes when \(k\) is the power of a prime and \(d\) is any positive integer, and some generalizations. We also use these results to show that \(Q_{5}\) divides \(K_{96}\).
We derive upper bounds for the number of edges in a triangle-free subgraph of a power of a cycle, extending results of an earlier paper by Bondy and Locke. In particular, the solution found for the case \(m = 20\) is a decomposition of \(3C^{20}_n\) into odd complete graphs.
The problem of maximizing the possible number of users of a packet radio network with time division multiplexing, when the number of slots per time frame and the maximum communication delay between users are given, can be modeled by a graph. In this paper, a new way of edge-coloring is presented on several families of large graphs on alphabets. This method allows us to obtain a certain improvement of the previous results.
An inductive process is used to find formulae for the number of 3-block configurations in BTD’s with parameters \((\mathcal{V}; \mathcal{B}; \mathcal{R}, p_1, p_2; 3; 2)\). In the process, a generating set of size nine is produced for the formulae. Because BIBD’s can be viewed as BTD’s with \(p_2 = 0\), once found, the BTD formulae yield the 3-block configuration formulae for BIBD’s with parameters \((v, b, r, 3, 2)\).
A directed triple system of order \(v\), denoted \(\text{DTS}(v)\), is said to be bicyclic if it admits an automorphism whose disjoint cyclic decomposition consists of two cycles. In this paper, we give necessary and sufficient conditions for the existence of bicyclic \(\text{DTS}(v)\)s.
The average distance in a connected weighted graph \(G\) is defined as the average of the distances between the vertices of \(G\). In 1985 P.M. Winkler [5] conjectured that every connected graph \(G\) contains an element \(e\), such that the removal of \(e\) enlarges the average distance by at most the factor \(\frac{4}{3}\).
D. Bienstock and E. Gyéri proved Winkler’s conjecture for the removal of an edge from a connected (unweighted) graph that has no vertices of degree one, and asked whether this conjecture holds for connected weighted graphs. In this paper we prove that any \(h\)-edge-connected weighted graph contains an edge whose removal does not increase the average distance by more than a factor of \(\frac{h}{h-1}\), \(h \geq 2\). This proves the edge-case of Winkler’s Conjecture for \(4\)-connected weighted graphs.
Furthermore, for \(3\)-edge-connected weighted graphs, it has been verified that the four-thirds conjecture holds for every weighted wheel \(W_p\), \(p \geq 4\), and for weighted \(K_{3,n}\) and \(K_{2,n}\) graphs for \(n \geq 2\).
A \((\Delta, D’, s)\)-digraph is a digraph with maximum out-degree \(\Delta\) such that after the deletion of any \(s\) of its vertices the resulting digraph has diameter at most \(D’\). Our concern is to find large, i.e. with order as large as possible, \((\Delta, D’, s)\)-digraphs. To this end, new families of digraphs satisfying a Menger-type condition are given. Namely, between any pair of non-adjacent vertices they have \(s + 1\) internally disjoint paths of length at most \(D’\). Then, new families of asymptotically optimal \((\Delta, D’, s)\)-digraphs are obtained.
Burr has shown that if \(G\) is any graph without isolates and \(H_0\) is any connected graph, every graph \(H\) obtained from \(H_0\) by subdividing a chosen edge sufficiently many times to create a long suspended path satisfies \(r(G, H) = (x(G) – 1)(|V(H)| – 1) + s(G)\), where \(s(G)\) is the largest number such that in every proper coloring of \(V(G)\) using \(\chi(G)\) colors, every color class has at least \(s(G)\) elements. In this paper, we prove a companion result for graphs obtained from \(H_0\) by adding sufficiently many pendant edges.
The Ramsey multiplicity \(R(G)\) of a graph \(G\) is defined as the smallest number of monochromatic copies of \(G\) in any two-coloring of the edges of \(K_r(q)\), where \(r(G)\) is the Ramsey number of \(G\). Here, we prove that \(R(K_4) \geq 4\).
In this paper we refine Whitney’s Theorem on \(k\)-connected graphs for \(k \geq 3\). In particular we show the following: Let \(G\) be a \(k\)-connected graph with \(k \geq 3\). For any two distinct vertices \(u\) and \(v\) of \(G\) there are \(k\) internally vertex disjoint paths \(P_1[u,v], P_2[u,v], \dots, P_k[u,v]\) such that \(G – V(P_i(u,v))\) is connected for \(i = 1, 2, \dots, k\), where \(P_i(u, v)\) denotes the internal vertices of the path \(P_i[u, v]\). Further one of the following properties holds:
In addition, some other properties will be proved.
Some results relating to the road-coloring conjecture of Alder, Goodwyn, and Weiss, which give rise to an \(O(n^2)\) algorithm to determine whether or not a given edge-coloring of a graph is a road-coloring, are noted. Probabilistic analysis is then used to show that, if the outdegree of every edge in an \(n\)-vertex digraph is \(\delta = \omega(\log n)\), a road-coloring for the graph exists. An equivalent re-statement of the conjecture is then given in terms of the cross-product of two graphs.
A graph \(G = (V, E)\) is a loop niche graph if there is a digraph \(D = (V, A)\)such that \(xy \in E\) iff there exists \(z \in V\) such that either \(xz\) and \(yz \in A\) or \(zx\) and \(zy \in A\). If \(D\) has no loops, \(G\) is a cyclic niche graph, and if \(D\) is acyclic, \(G\) is a niche graph. We give a characterization of triangle-free cyclic niche graphs, and apply this to classify grids.
Let \(\Phi(N)\) be the maximum number of simple polygons that can be drawn using as vertices a set \(V\) of \(N\) points in the plane. By counting the number of simple polygons of a particular configuration of \(V\), an improved lower bound for \(\Phi(N)\) is obtained. It is proved that \(\Phi(N)^\frac{1}{N}\) is asymptotically greater than \(3.6\).
1970-2025 CP (Manitoba, Canada) unless otherwise stated.