We show that the edges of a planar 3-connected graph with $n$ vertices can be covered by at most $[(n+1)/2]$ cycles. This proves a special case of a conjecture of Bondy that the edges of a 2-connected graph can be covered by at most $(2n–1)/3$ cycles.

In [J. of Combinatorial Theory (B),40(1986),229-230], Fleischner proved that if $G$ is a $2$-edge-connected planar graph and if ${\mathcal{C}}_0=\{C_1,\dots ,C_k\}$ is a collection of edge-disjoint cycles of $G$, then $G$ has a cycle double cover $\mathcal{C}$ that contains ${\mathcal{C}}_0$. In this note, we show that this holds also for graphs that do not have a subgraph contractible to $K_5$.

Given a binary code $C$, the set $K$ of all vectors which leave $C$ invariant under translation is called the kernel of $C$. The main concern of this paper is the development of an efficient algorithm for computing the kernel of $C$. We present such an algorithm with runtime $O(|C|\log |C|)$, which is the best possible.

The intersection problem for a pair of transitive triple systems (or $2-(\nu ,3,1)$ directed designs) was solved by Lindner and Wallis, and independently by H.L. Fu, in 1982-1983. In this paper, we determine the intersection problem for a pair of $2-(\nu ,4,1)$ directed designs.

Let $H_a^1=\{v:v\ge a,v\equiv 0,1(\mathrm{mod}a)\}$. It is well known that such sets are PBD-closed. Finite bases are found for these sets for $a=6,7,$ and $8$. At the same time, we improve the result of Mullin in [6] about finite bases of $H^a=\{v:v\ge a+1,v\equiv 1(\mathrm{mod}a)\}$ for $a=5$ and $6$.

Let $G$ be a $2$-edge-connected graph and $v$ be a vertex of $G$, and $F\subset F^{\prime }\subset E(v)$ such that $1\le |F|$ and $|F|+2=|F^{\prime }|\le d(v)–1$. Then there is a subset $F^{\ast }$ such that $F\subset F^{\ast }\subset F^{\prime }$ (here, $|F^{\ast }|=|F|+1$), and the graph obtained from $G$ by splitting the edges of $F^{\ast }$ away from $v$ remains $2$-edge-connected unless $v$ is a cut-vertex of $G$. This generalizes a very useful Vertex-Splitting Lemma of Fleischner.
Let $\mathcal{C}$ be a circuit cover of a bridge-less graph $G$. The depth of $\mathcal{C}$ is the smallest integer $k$ such that every vertex of $G$ is contained in at most $k$ circuits of $\mathcal{C}$. It is conjectured by L. Pyber that every bridge-less graph $G$ has a circuit cover $\mathcal{C}$ such that the depth of $\mathcal{C}$ is at most $\mathrm{\Delta }(G)$. In this paper, we prove that

1. every bridge-less graph $G$ has a circuit cover $\mathcal{C}$ such that the depth of $\mathcal{C}$ is at most $\mathrm{\Delta }(G)+2$ and
2. if a bridge-less graph $G$ admits a nowhere-zero $4$-flow or contains no subdivision of the Petersen graph, then $G$ has a circuit cover $\mathcal{C}$ such that the depth of $\mathcal{C}$ is at most $2\lceil 2\mathrm{\Delta }(G)/3\rceil$.

Let $m\ge 1$ be an integer and let $G$ be a graph of order $n$. A set $\mathcal{D}$ of vertices of $G$ is an $m$-dominating set of $G$ if every vertex of $V(G)–\mathcal{D}$ is within distance $m$ from some vertex of $\mathcal{D}$. An independent set of vertices of $G$ is a set of vertices of $G\$whoseelementsarepairwisenonadjacent.Theminimumcardinalityamongallindependent\text{(}m$-dominating sets of $G$ is called the independent $m$-domination number and is denoted by $id(m,G)$. We show that if $G$ is a connected graph of order $n\ge m+1$, then $id(m,G)\le (n+m+1-2\sqrt{n}/m),$ and this bound is sharp.

Several theorems about Hamiltonian, pan-cyclic and other properties of locally semi-complete digraphs are obtained in this paper.

In the $n$-dimensional hypercube, an $n$-snake is a simple path with no chords, while an $n$-coil is a simple cycle without chords. There has been much interest in determining the length of a maximum $n$-snake and a maximum $n$-coil. Only upper and lower bounds for these maximum lengths are known for arbitrary $n$. Computationally, the problem of finding maximum $n$-snakes and $n$-coils suffers from combinatorial explosion, in that the size of the solution space which must be searched grows very rapidly as $n$ increases. Previously, the maximum lengths of $n$-snakes and $n$-coils have been established only for $n\le 7$and $n\le 6$, respectively. In this paper, we report on a coil searching computer program which established that $48$ is the maximum length of a coil in the hypercube of dimension $7$.

The complements of the perfect dominating sets of the $n$-cube, for $n\le 8$, are characterized as well as some outstanding vertex-spanning edge-partitions of them involving the Fano plane, as a contribution to the study of distance-preserving regular subgraphs of hypercubes.

A graph is said to be in $L_1$ if $\mathrm{deg}(u)+\mathrm{deg}(v)\ge |N(u)\cup N(w)\cup N(v)|–1$ for each induced path $uwv$ of order three. We prove that a $2$-connected graph $G$ in $L_1$ of diameter two is hamiltonian, or $K_{d,d+1}\subset G\subset K_d+(d+1)K_1$ for some $d\ge 2$. This theorem generalizes a couple of known sufficient conditions for a graph to be hamiltonian. We also discuss the relation between this theorem and several other degree conditions for hamiltonicity.

On the basis of circuit uniqueness, the concept of strong circuit uniqueness is introduced, and some graphs with the property of strong circuit uniqueness are identified. The results are then used to prove successfully the circuit uniqueness of the graphs $K_m\cup K_n$ and $K_{m,n}$. This represents an improvement on the previous papers on the same subject.

Several criteria have been proposed as desirable for binary cryptographic functions. Three important ones are balance, correlation-immunity, and higher order strict avalanche criterion. Lloyd [7] has shown that there are no balanced, uncorrelated functions which satisfy the strict avalanche criterion of order $n-2$. In this note, we give a short proof of this result using elementary combinatorial arguments. The proof relies on the solution of a recurrence relation that seems to be of interest in its own right.

In this paper, we introduce some concepts relating to idempotent ordered orthogonal quasigroups (IOOQ), ordered orthogonal Steiner triple systems (ordered OSTS), and ordered orthogonal group divisible designs (ordered OGDD), and use them to obtain some construction methods for OGDD.

It is known that triangle-free graphs of diameter $2$ are just maximal triangle-free graphs. Kantor ([5]) showed that if $G$ is a triangle-free and $4$-cycle free graph of diameter $2$, then $G$ is either a star or a Moore graph of diameter $2$; if $G$ is a $4$-cycle free graph of diameter $2$ with at least one triangle, then $G$ is either a star-like graph or a polarity graph (defined from a finite projective plane with polarities) of order $r^2+r+1$ for some positive integer $r$ (or $P_r$-\emph{graph} for short). We study, by purely graph theoretical means, the structure of $P_r$-graphs and construct $P_r$-graphs for small values of $r$. Further, we characterize graphs of diameter $2$ without $5$-cycles and $6$-cycles, respectively. In general, one can characterize $C_k$-free graphs of diameter $2$ with $k>6$ with a similar approach.

Dey’s formula can be used to count the subgroups of finitely generated groups and to establish congruence properties of subgroup counting functions. We develop an algebraic technique based on this formula for counting the subgroups of given index in Hecke groups, and show how to streamline it for efficient computation modulo $2$.

A simple graph $G$ with a perfect matching is said to be \emph{$k$-extendable} if for every set $M$ of $k$ independent edges, there exists a perfect matching in $G$ containing all the edges of $M$. In an earlier paper, we characterized $(n-2)$-extendable graphs on $2n\ge 10$ vertices. In this paper, we complete the characterization by resolving the remaining small cases of $2n=6$ and $8$. In addition, the subclass of $k$-extendable graphs that are “critical” and “minimal” are determined.

Given a graph $G=(V,E)$ and a vertex subset $D\subseteq V$, a subset $S\subseteq V$ is said to realize a “parity assignment” $D$ if for each vertex $v\in V$ with closed neighborhood $N[v]$ we have that $|N[v]\cap S|$ is odd if and only if $v\in D$. Graph $G$ is called all parity realizable if every parity assignment $D$ is realizable. This paper presents some examples and provides a constructive characterization of all parity realizable trees.

The set of all possible intersection sizes between two simple triple systems $TS(v,{\lambda }_1)$ and $TS(v,{\lambda }_2)$ is denoted by $Int(v,{\lambda }_1,{\lambda }_2)$. In this paper, for $6\le v\le 14$, and for all feasible $\lambda {\$}^{\prime }s,\text{(}Int(v,{\lambda }_1,{\lambda }_2)$ is determined.

In this paper we obtain further results on the Multiplier Conjecture for the case $n=2n_1$, using our method.

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\ge 1$ 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$. If no such integer $n$ exists, the greatest common divisor index of $G$ is infinite. Several graphs are shown to have infinite greatest common divisor index, including matchings, stars, small paths, and the cycle $C_4$. It is shown for an edge-transitive graph $F$ of order $p$ with vertex independence number less than $p/2$ that if $G$ is an $F$-decomposable graph of sufficiently large size, then $G$ is also $(F–e)\cup K_2-$decomposable. From this it follows that each such edge-transitive graph has finite index. In particular, all complete graphs of order at least $3$ are shown to have greatest common divisor index $1$ and the greatest common divisor index of the odd cycle $C_{2k+1}$ lies between $k$ and $4k^2–2k–1$. The graphs $K_p–e$, $p\ge 3$, have infinite or finite index depending on the value of $p$; in particular, $K_p–e$ has infinite index if $p\le 5$ and index $1$ if $p\ge 6$.

We prove that the set edge-reconstruction conjecture is true for graphs with at most two graphs in the set of edge-deleted subgraphs.

We determine all borders of the $n\underset{\_}{th}$ Fibonacci string, $f_n$, for $n\ge 3$. In particular, we give two proofs that the longest border of $f_n$ is $f_{n-2}$. One proof is independent of the Defect Theorem.