Amply regular graphs and block designs

We study the amply regular diameter d graphs Γ such that for some vertex a the set of vertices at distance d from a is the set of points of a 2-design whose set of blocks consists of the intersections of the neighborhoods of points with the set of vertices at distance d-1 from a. We prove that the subgraph induced by the set of points is a clique, a coclique, or a strongly regular diameter 2 graph. For diameter 3 graphs we establish that this construction is a 2-design for each vertex a if and only if the graph is distance-regular and for each vertex a the subgraph Γ₃(a) is a clique, a coclique, or a strongly regular graph. We obtain the list of admissible parameters for designs and diameter 3 graphs under the assumption that the subgraph induced by the set of points is a Seidel graph. We show that some of the parameters found cannot correspond to distance-regular graphs.     

Regular pseudo-median graphs

A graph is pseudo-median if for every triple u, v, w of vertices there exists either a unique vertex between each pair of them (if their mutual distances sum up to an even number) or a unique triangle whose edges lie between the three pairs of u, v, w, respectively (if the distance sum is odd). We show that a finite pseudo-median graph is regular if and only if it is the Cartesian product of a hypercube with either a complete graph or a hyper-octahedron. Every self-map of a pseudo-median graph that preserves or collapses edges has an invariant regular pseudo-median subgraph. Furthermore, the set of all vertices minimizing the total distance to the vertices of a pseudo-median graph induces a regular pseudo-median subgraph.     

Large cliques or stable sets in graphs with no four‐edge path and no five‐edge path in the complement

Erd?s and Hajnal [Discrete Math 25 (1989), 37–52] conjectured that, for any graph H, every graph on n vertices that does not have H as an induced subgraph contains a clique or a stable set of size n^?(H) for some ?(H)>0. The Conjecture 1. known to be true for graphs H with |V(H)|≤4. One of the two remaining open cases on five vertices is the case where H is a four‐edge path, the other case being a cycle of length five. In this article we prove that every graph on n vertices that does not contain a four‐edge path or the complement of a five‐edge path as an induced subgraph contains either a clique or a stable set of size at least n^1/6. © 2011 Wiley Periodicals, Inc. J Graph Theory     

A construction of chromatic index critical graphs

We prove that if K is an undirected, simple, connected graph of even order which is of class one, regular of degree p ≥ 2 and such that the subgraph induced by any three vertices is either connected or null, then any graph G obtained from K by splitting any vertex is p-critical. We find that various constructions of critical graphs by S. Fiorini are special cases of a corollary of this result.     

Balanced group-labeled graphs

A group-labeled graph is a graph whose vertices and edges have been assigned labels from some abelian group. The weight of a subgraph of a group-labeled graph is the sum of the labels of the vertices and edges in the subgraph. A group-labeled graph is said to be balanced if the weight of every cycle in the graph is zero. We give a characterization of balanced group-labeled graphs that generalizes the known characterizations of balanced signed graphs and consistent marked graphs. We count the number of distinct balanced labellings of a graph by a finite abelian group $\Gamma$ and show that this number depends only on the order of $\Gamma$ and not its structure. We show that all balanced labellings of a graph can be obtained from the all-zero labeling using simple operations. Finally, we give a new constructive characterization of consistent marked graphs and markable graphs, that is, graphs that have a consistent marking with at least one negative vertex.     

Exotic n-universal graphs

An n-universal graph is a graph that contains as an induced subgraph a copy of every graph on n vertices. It is shown that for each positive integer n > 1 there exists an n-universal graph G on 4ⁿ - 1 vertices such that G is a (v, k, λ)-graph, and both G and its complement G¯ are 1-transitive in the sense of W. T. Tutte and are of diameter 2. The automorphism group of G is a transitive rank 3 permutation group, i.e., it acts transitively on (1) the vertices of G, (2) the ordered pairs uv of adjacent vertices of G, and (3) the ordered pairs xy of nonadjacent vertices of G.     

Automorphism groups of graphs with forbidden subgraphs

For a graph Ф letF(Ф) be the class of finite graphs which do not contain an induced subgraph isomorphic to Ф. We show that whenever Ф is not isomorphic to a path on at most 4 vertices or to the complement of such a graph then for every finite groupG there exists a graph ГєF(Ф) such thatG is isomorphic to the automorphism group of Г. For all paths д on at most 4 vertices we determine the class of all automorphism groups of members ofF(д).     

Representing groups by graphs with constant link and hypergraphs

A graph L is called a link graph if there is a graph G such that for each vertex of G its neighbors induce a subgraph isomorphic to L. Such a G is said to have constant link L. We prove that for any finite group Γ and any disconnected link graph L with at least three vertices there are infinitely many connected graphs G with constant link L and AutG ? Γ. We look at the analogous problem for connected link graphs, namely, link graphs that are paths or have disconnected complements. Furthermore we prove that for n, r ≥ 2, but not n = 2 = r, any finite group can be represented by infinitely many connected r-uniform, n-regular hypergraphs of arbitrarily large girth.     

Supereulerian complementary graphs

Nebeský in [12] show that for any simple graph with n ≥ 5 vertices, either G or G^c contains an eulerian subgraph with order at least n - 1, with an explicitly described class of exceptional graphs. In this note, we show that if G is a simple graph with n ≥ 61 vertices, then either G or G^c is supereulerian, with some exceptions. We also characterize all these exceptional cases. These results are applied to show that if G is a simple graph with n ≥ 61 vertices such that both G and G^c are connected, then either G or G^c has a 4-flow, or both G and G^c have cut-edges. © 1993 John Wiley & Sons, Inc.     

Cores of Imprimitive Symmetric Graphs of Order a Product of Two Distinct Primes

A retract of a graph Γ is an induced subgraph Ψ of Γ such that there exists a homomorphism from Γ to Ψ whose restriction to Ψ is the identity map. A graph is a core if it has no nontrivial retracts. In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph Γ is G‐symmetric if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of Γ admits a nontrivial partition that is preserved by G, then Γ is an imprimitive G‐symmetric graph. In this paper cores of imprimitive symmetric graphs Γ of order a product of two distinct primes are studied. In many cases the core of Γ is determined completely. In other cases it is proved that either Γ is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given.     

Note on induced subgraphs of the unit distance graphE n

The unit distance graphE ⁿ is the graph whose vertices are the points in Euclideann-space, and two vertices are adjacent if and only if the distance between them is 1. We prove that for anyn there is a finite bipartite graph which cannot be embedded inE ⁿ as an induced subgraph and that every finite graph with maximum degreed can be embedded inE ^N ,N=(d ³ –d)/2, as an induced subgraph.     

On the connectedness of the complement of a ball in distance-regular graphs

An important property of strongly regular graphs is that the second subconstituent of any primitive strongly regular graph is always connected. Brouwer asked to what extent this statement can be generalized to distance-regular graphs. In this paper, we show that if γ is any vertex of a distance-regular graph Γ and t is the index where the standard sequence corresponding to the second largest eigenvalue of Γ changes sign, then the subgraph induced by the vertices at distance at least t from γ, is connected.     

Random mappings of scaled graphs

Given a connected finite graph Γ with a fixed base point O and some graph G with a based point we study random 1-Lipschitz maps of a scaled Γ into G. We are mostly interested in the case where G is a Cayley graph of some finitely generated group, where the construction does not depend on the choice of base points. A particular case of Γ being a graph on two vertices and one edge corresponds to the random walk on G, and the case where Γ is a graph on two vertices and two edges joining them corresponds to Brownian bridge in G. We show, that unlike in the case ${G=\mathbb Z^d}$ , the asymptotic behavior of a random scaled mapping of Γ into G may differ significantly from the asymptotic behavior of random walks or random loops in G. In particular, we show that this occurs when G is a free non-Abelian group. Also we consider the case when G is a wreath product of ${\mathbb Z}$ with a finite group. To treat this case we prove new estimates for transition probabilities in such wreath products. For any group G generated by a finite set S we define a functor E from category of finite connected graphs to the category of equivalence relations on such graphs. Given a finite connected graph Γ, the value E _G,S (Γ) can be viewed as an asymptotic invariant of G.     

On a conjecture of Brouwer involving the connectivity of strongly regular graphs

In this paper, we study a conjecture of Andries E. Brouwer from 1996 regarding the minimum number of vertices of a strongly regular graph whose removal disconnects the graph into non-singleton components.We show that strongly regular graphs constructed from copolar spaces and from the more general spaces called Δ-spaces are counterexamples to Brouwer?s Conjecture. Using J.I. Hall?s characterization of finite reduced copolar spaces, we find that the triangular graphs T(m), the symplectic graphs Sp(2r,q) over the field Fq (for any q prime power), and the strongly regular graphs constructed from the hyperbolic quadrics O⁺(2r,2) and from the elliptic quadrics O⁻(2r,2) over the field F₂, respectively, are counterexamples to Brouwer?s Conjecture. For each of these graphs, we determine precisely the minimum number of vertices whose removal disconnects the graph into non-singleton components. While we are not aware of an analogue of Hall?s characterization theorem for Δ-spaces, we show that complements of the point graphs of certain finite generalized quadrangles are point graphs of Δ-spaces and thus, yield other counterexamples to Brouwer?s Conjecture.We prove that Brouwer?s Conjecture is true for many families of strongly regular graphs including the conference graphs, the generalized quadrangles GQ(q,q) graphs, the lattice graphs, the Latin square graphs, the strongly regular graphs with smallest eigenvalue −2 (except the triangular graphs) and the primitive strongly regular graphs with at most 30 vertices except for few cases.We leave as an open problem determining the best general lower bound for the minimum size of a disconnecting set of vertices of a strongly regular graph, whose removal disconnects the graph into non-singleton components.     

On some minimal graphs of the torus

Let Γ be the set of finite, simple and nondirected graphs being not embeddable into the torus. Furthermore let >⁴ be a partial order-relation and M⁴ (Γ) the minimal basis of Γ. In this paper we determine three graphs of M⁴ (Γ) being embeddable into the projective plane and containing the subgraph W.     

Two distance-regular graphs

We construct two families of distance-regular graphs, namely the subgraph of the dual polar graph of type B ₃(q) induced on the vertices far from a fixed point, and the subgraph of the dual polar graph of type D ₄(q) induced on the vertices far from a fixed edge. The latter is the extended bipartite double of the former.     

Almost self-centered graphs

The center of a graph is the set of vertices with minimum eccentricity. Graphs in which all vertices are central are called self-centered graphs. In this paper almost self-centered (ASC) graphs are introduced as the graphs with exactly two non-central vertices. The block structure of these graphs is described and constructions for generating such graphs are proposed. Embeddings of arbitrary graphs into ASC graphs are studied. In particular it is shown that any graph can be embedded into an ASC graph of prescribed radius. Embeddings into ASC graphs of radius two are studied in more detail. ASC index of a graph G is introduced as the smallest number of vertices needed to add to G such that G is an induced subgraph of an ASC graph.     

Induced embeddings in Steinhaus graphs

Fix any positive integer n. Let S be the set of all Steinhaus graphs of order n(n − 1)/2 + 1. The vertices for each graph in S are the first n(n − 1)/2 + 1 positive integers. Let I be the set of all labeled graphs of order n with vertices of the form i(i − 1)/2 + 1 for the first n positive integers i. This article shows that the function ϕ : S → I that maps a Steinhaus graph to its induced subgraph is a bijection. Therefore, any graph of order n is isomorphic to an induced subgraph of a Steinhaus graph of order n(n − 1)/2 + 1. This considerably tightens a result of Brigham, Carrington, and Dutton in [Brigham, Carrington, & Dutton, Combin. Inform. System Sci. 17 (1992)], which showed that this could be done with a Steinhaus graph of order 2ⁿ⁻¹. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 1–9, 1998     

Unavoidable Configurations in Complete Topological Graphs

A topological graph is a graph drawn in the plane so that its vertices are represented by points, and its edges are represented by Jordan curves connecting the corresponding points, with the property that any two curves have at most one point in common. We define two canonical classes of topological complete graphs, and prove that every topological complete graph with n vertices has a canonical subgraph of size at least clog^1/8 n, which belongs to one of these classes. We also show that every complete topological graph with n vertices has a non-crossing subgraph isomorphic to any fixed tree with at most clog^1/6 n vertices.     

Three-regular subgraphs of four-regular graphs

Berge conjectured that every finite simple 4-regular graph G contains a 3-regular subgraph. We prove that this conjecture is true if the cyclic edge connectivity λ^c(G) of G is at least 10. Also we prove that if G is a smallest counterexample, then λ^c(G) is either 6 or 8.