Antipodal graphs of diameter three

Distance-regular graphs of diameter three are of three (almost distinct) kinds: primitive, bipartite, and antipodal. An antipodal graph of diameter three is just an r-fold covering of a complete graph K_k+1 for some r?k. Its intersection array and spectrum are determined by the parameters r, k together with the number c of 2-arcs joining any two vertices at distance two. Most such graphs have girth three. In this note we consider antipodal distance-regular graphs of diameter three and girth ? 4. If r=2, then the only graphs are “K_{k+1, k+1} minus a 1-factor.” We therefore assume r?3. The graphs with c=1 necessarily have r=k and were classified in lsqb3rsqb. We prove the inequality $\text{r?2>c}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ (Theorem 2), list the feasible parameter sets when c=2 or 3 (Corollary 1), and conclude that every 3-fold or 4-fold antipodal covering of a complete graph has girth three (Corollary 2).     

The diameter of bipartite distance-regular graphs

It is shown that any bipartite distance-regular graph with finite valency k and at least one cycle is finite, with diameter d and girth g satisfying $\text{d≤}\text{(k?1)(g?2)}\text{2+1}$. In particular, the number of bipartite distance-regular graphs with fixed valency and girth is finite.     

On k-sequential and other numbered graphs

The concept of a k-sequential graph is presented as follows. A graph G with ∣V(G)∪ E(G)∣=t is called k-sequential if there is a bijection$\text{?: V(G)∪E(G) → {k,k+1,…,t+k?1}}$ such that for each edge$\text{e}\text{?}\text{=xy}$in E(G) one has$\text{?(}\text{e}\text{?}\text{) = ∣?(x)??(y)∣}$. A graph that is 1-sequential is called simply sequential, and, in particular the author has conjectured that all trees are simply sequential. In this paper an introductory study of k-sequential graphs is made. Further, several variations on the problems of gracefully or sequentially numbering the elements of a graph are discussed.     

Max-cut and extendability of matchings in distance-regular graphs

A connected graph $G$ of even order $v$ is called $t$-extendable if it contains a perfect matching, $t<v/2$ and any matching of $t$ edges is contained in some perfect matching. The extendability of $G$ is the maximum $t$ such that $G$ is $t$-extendable. Since its introduction by Plummer in the 1980s, this combinatorial parameter has been studied for many classes of interesting graphs. In 2005, Brouwer and Haemers proved that every distance-regular graph of even order is $1$-extendable and in 2014, Cioabă and Li showed that any connected strongly regular graph of even order is 3-extendable except for a small number of exceptions.In this paper, we extend and generalize these results. We prove that all distance-regular graphs with diameter $D\ge 3$ are 2-extendable and we also obtain several better lower bounds for the extendability of distance-regular graphs of valency $k\ge 3$ that depend on $k$, $\lambda$ and $\mu$, where $\lambda$ is the number of common neighbors of any two adjacent vertices and $\mu$ is the number of common neighbors of any two vertices in distance two. In many situations, we show that the extendability of a distance-regular graph with valency $k$ grows linearly in $k$. We conjecture that the extendability of a distance-regular graph of even order and valency $k$ is at least $\lceil k/2\rceil -1$ and we prove this fact for bipartite distance-regular graphs.In course of this investigation, we obtain some new bounds for the max-cut and the independence number of distance-regular graphs in terms of their size and odd girth and we prove that our inequalities are incomparable with known eigenvalue bounds for these combinatorial parameters.     

The number of Hamiltonian circuits

G = 〈V(G), E(G)〉 denotes a directed graph without loops and multiple arrows. $\text{K}$(G) denotes the set of all Hamiltonian circuits of G. Put H(n, r) = max{|E(G)|, |V(G)| = n, 1 ≤ |$\text{K}$(G)| ≤ r}. Theorem: $\text{H(n, 1) = (}\text{n}{}^2\text{2}\text{) + (}\text{n}\text{2}\text{) ?1}$. Further, H(n, 2),…, H(n, 5) are given.     

Solving NP-hard problems in ‘almost trees’: Vertex cover

We present an algorithm which finds a minimum vertex cover in a graph G(V, E) in time $\text{O}\text{(|V|+(}\text{a}\text{k}\text{)2}{}^{\mathrm{<mtext>k</mtext><mtext>3</mtext>}}\text{)}$, where for connected graphs G the parameter a is defined as the minimum number of edges that must be added to a tree to produce G, and k is the maximum a over all biconnected components of the graph. The algorithm combines two main approaches for coping with NP-completeness, and thereby achieves better running time than algorithms using only one of these approaches.     

Regular subgraphs of almost regular graphs

Suppose every vertex of a graph G has degree k or k + 1 and at least one vertex has degree k + 1. It is shown that if k ≥ 2q ? 2 and q is a prime power then G contains a q-regular subgraph (and hence an r-regular subgraph for all r < q, r ≡ q (mod 2)). It is also proved that every simple graph with maximal degree Δ ≥ 2q ? 2 and average degree $\text{d > (}\text{(2q ? 2)}\text{(2q ? 1)}\text{)(Δ + 1)}$, where q is a prime power, contains a q-regular subgraph (and hence an r-regular subgraph for all r < q, r ≡ q (mod 2)). These results follow from Chevalley's and Olson's theorems on congruences.     

Tough graphs and hamiltonian circuits

The toughness of a graph G is defined as the largest real number t such that deletion of any s points from G results in a graph which is either connected or else has at most s/t components. Clearly, every hamiltonian graph is 1-tough. Conversely, we conjecture that for some t₀, every t₀-tough graph is hamiltonian. Since a square of a k-connected graph is always k-tough, a proof of this conjecture with t₀ = 2 would imply Fleischner's theorem (the square of a block is hamiltonian). We construct an infinite family of ($\text{3}\text{2}$)-tough nonhamiltonian graphs.     

A relationship between the diameter and the intersection number c 2 for a distance-regular graph

In this paper we will look at the relationship between the intersection number c ₂ and the diameter of a distance-regular graph. We also give some tools to show that a distance-regular graph with large c ₂ is bipartite, and a tool to show that if k _D is too small then the distance-regular graph has to be antipodal.     

Connected matroids with the smallest whitney numbers

In “The Slimmest Geometric Lattices” (Trans. Amer. Math. Soc.). Dowling and Wilson showed that if G is a combinatorial geometry of rank r(G) = n, and if _X(G) = Σμ(0, x)λ^{r ? r(x)} = Σ (?1)^{r ? k}W_kλ^k is the characteristic polynomial of G, then

$\text{w}{}_{\mathrm{k}}\text{?}\text{r}\text{k}\text{+n}\text{r?1}\text{k}$

Thus γ(G) ? 2^{r ? 1} (n+2), where γ(G) = Σw_k. In this paper we sharpen these lower bounds for connected geometries: If G is connected, r(G) ? 3, and n(G) ? 2 ((r, n) ≠ (4,3)), then

$\text{w}{}_{\mathrm{i}}\text{?}\text{r}\text{i}\text{+ n}\text{r}\text{i+1}\text{for i>1; w}{}_1\text{?r+n}\text{r}\text{2}\text{? 1;}$

|μ| ? (r? 1)n; and γ ? (2^{r ? 1} ? 1)(2n + 2). These bounds are all achieved for the parallel connection of an r-point circuit and an (n + 1)point line. If G is any series-parallel network, $\text{r(G) = r(}\text{G}\text{?}\text{) = 4}$, and $\text{n(G) = n(}\text{G}\text{?}\text{) = 3}$ then $\text{(w}{}_1\text{(G))}{}^4{}_{\mathrm{t-G}}\text{? (w}{}_1\text{(}\text{G}\text{?}\text{)) = (8, 20, 18, 7, 1)}$. Further, if β is the Crapo invariant,

$\text{β(G)=}\text{d}{}_{\mathrm{X}}\text{(G)}\text{dλ}\text{(1)}\text{,}$

then β(G) ? max(1, n ? r + 2). This lower bound is achieved by the parallel connection of a line and a maximal size series-parallel network.     

Graph equations for line graphs,total graphs,middle graphs and quasi-total graphs

Let G be a graph with vertex-set V(G) and edge-set X(G). Let L(G) and T(G) denote the line graph and total graph of G. The middle graph M(G) of G is an intersection graph Ω(F) on the vertex-set V(G) of any graph G. Let F = V′(G) ∪ X(G) where V′(G) indicates the family of all one-point subsets of the set V(G), then $\text{M(G) = Ω(F)}$.The quasi-total graph P(G) of G is a graph with vertex-set V(G)∪X(G) and two vertices are adjacent if and only if they correspond to two non-adjacent vertices of G or to two adjacent edges of G or to a vertex and an edge incident to it in G.In this paper we solve graph equations $\text{L(G) ? P(H);}\text{L(G)}\text{? P(H); P(G) ? T(H);}\text{P(G)}\text{? T(H); M(G) ? P(H);}\text{M(G)}\text{? P(H)}$.     

A sufficient condition for hamiltonian circuits

A theorem is proved that is (in a sense) the best possible improvement on the following theme: If G is an undirected graph on n vertices in which $\text{|Γ(S)| ≥}\text{1}\text{3}\text{(n + | S | + 3)}$ for every non-empty subset S of the vertices of G, then G is Hamiltonian.     

Independence in graphs with maximum degree four

Let $\text{C}$ be the class of triangle-free graphs with maximum degree four. A lower bound for the number of edges in a graph of $\text{C}$ is derived in terms of its order p and independence β. Also a characterization of certain minimum independence graphs in $\text{C}$ is provided. Let r(k) be the smallest integer such that every graph in $\text{C}$ with at least r(k) vertices has independence at least k. The values of r(k) for all k may be derived from our main theorem and $\text{4}\text{13}$ obtained as the best possible lower bound for the independence ratio $\text{β}\text{p}$ of graphs in $\text{C}$.     

Edge-distance-regular graphs

Edge-distance-regularity is a concept recently introduced by the authors which is similar to that of distance-regularity, but now the graph is seen from each of its edges instead of from its vertices. More precisely, a graph Γ with adjacency matrix A is edge-distance-regular when it is distance-regular around each of its edges and with the same intersection numbers for any edge taken as a root. In this paper we study this concept, give some of its properties, such as the regularity of Γ, and derive some characterizations. In particular, it is shown that a graph is edge-distance-regular if and only if its k-incidence matrix is a polynomial of degree k in A multiplied by the (standard) incidence matrix. Also, the analogue of the spectral excess theorem for distance-regular graphs is proved, so giving a quasi-spectral characterization of edge-distance-regularity. Finally, it is shown that every nonbipartite graph which is both distance-regular and edge-distance-regular is a generalized odd graph.     

A short note about pursuit games played on a graph with a given genus

On a finite simple graph G = (X,E), p players pursuers $\text{A}{}_1\text{, ∴, A}{}_{\mathrm{p}}$ and one player evader B who move in turn along the edges of G are considered. The p pursuers $\text{A}{}_1\text{, ∴, A}{}_{\mathrm{p}}$ want to catch B who tries to escape. R. Nowakowski and P. Winkler [Discrete Math.43 (1983), 235–240] and A. Quilliot [“Thèse de 3° cycle,” pp. 131–145, Université de Paris VI, 1978] already characterized the graphs such that one pursuer is sufficient to catch the evader B. Very recently, M. Aigner and M. Fromme [Appl. Discrete Math., in press] proved that if G is a planar graph, three pursuers are sufficient to catch the evader B. This result is extended, showing that if G is a graph with a given genus k, then 3 + 2k pursuers are enough to “arrest” the evader B.