Geometric aspects of 2-walk-regular graphs

A t-walk-regular graph is a graph for which the number of walks of given length between two vertices depends only on the distance between these two vertices, as long as this distance is at most t. Such graphs generalize distance-regular graphs and t-arc-transitive graphs. In this paper, we will focus on 1- and in particular 2-walk-regular graphs, and study analogues of certain results that are important for distance-regular graphs. We will generalize Delsarte?s clique bound to 1-walk-regular graphs, Godsil?s multiplicity bound and Terwilliger?s analysis of the local structure to 2-walk-regular graphs. We will show that 2-walk-regular graphs have a much richer combinatorial structure than 1-walk-regular graphs, for example by proving that there are finitely many non-geometric 2-walk-regular graphs with given smallest eigenvalue and given diameter (a geometric graph is the point graph of a special partial linear space); a result that is analogous to a result on distance-regular graphs. Such a result does not hold for 1-walk-regular graphs, as our construction methods will show.     

On graphs with small subgraphs of large chromatic number

Bollobás, Erdös, Simonovits, and Szemerédi conjectured [1] that for each positive constantc there exists a constantg(c) such that ifG is any graph which cannot be made 3-chromatic by the omission ofcn ² edges, thenG contains a 4-chromatic subgraph with at mostg(c) vertices. Here we establish the following generalization which was suggested by Erdös [2]: For each positive constantc and positive integerk there exist positive integersf _k(c) andn _o such that ifG is any graph with more thann _o vertices having the property that the chromatic number ofG cannot be made less thank by the omission of at mostcn ² edges, thenG contains ak-chromatic subgraph with at mostf _k(c) vertices.     

On the Ramsey number of trees versus graphs with large clique number

Chvátal established that r(T_m, K_n) = (m – 1)(n – 1) + 1, where T_m is an arbitrary tree of order m and K_n is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed K_n could be replaced by a graph with clique number n and order n + 1 provided n ≧ 3 and m ≧ 3. We further extend these results to show that K_n can be replaced by any graph on n + 2 vertices with clique number n, provided n ≧ 5 and m ≧ 4. We then show that further extensions, in particular to graphs on n + 3 vertices with clique number n are impossible. We also investigate the Ramsey number of trees versus complete graphs minus sets of independent edges. We show that r(T_m, K_n –tK₂) = (m – 1)(n – t – 1) + 1 for m ≧ 3, n ≧ 6, where T_m is any tree of order m except the star, and for each t, O ≦ t ≦ [(n – 2)/2].     

On embedding of finite distance graphs with large chromatic number in random graphs

The paper studies the problem indicated in the title, which arises in connection with the well-known Nelson–Erdös–Hadwiger problem of finding the chromatic number of the Euclidean space.     

Sweeping graphs with large clique number

Searching a network for intruders is an interesting and often difficult problem. Sweeping (or edge searching) is one such search model, in which intruders may exist anywhere along an edge. It was conjectured that graphs exist for which the connected sweep number is strictly less than the monotonic connected sweep number. We prove that this is true, and the difference can be arbitrarily large. We also show that the clique number is a lower bound on the sweep number.     

On planar intersection graphs with forbidden subgraphs

Let be a family of n compact connected sets in the plane, whose intersection graph has no complete bipartite subgraph with k vertices in each of its classes. Then has at most n times a polylogarithmic number of edges, where the exponent of the logarithmic factor depends on k. In the case where consists of convex sets, we improve this bound to O(n log n). If in addition k = 2, the bound can be further improved to O(n). © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 205–214, 2008     

Nearly bipartite graphs with large chromatic number

P. Erdős and A. Hajnal asked the following question. Does there exist a constant ε>0 with the following property: If every subgraphH of a graphG can be made bipartite by the omission of at most ε|H| edges where |H| denotes the number of vertices ofH thenx(H) ≦ 3. The aim of this note is to give a negative answer to this question and consider the analogous problem for hypergraphs. The first was done also by L. Lovász who used a different construction.     

Distance graphs with large chromatic number and without large cliques

The present paper is devoted to the study of the properties of distance graphs in Euclidean space. We prove, in particular, the existence of distance graphs with chromatic number of exponentially large dimension and without cliques of dimension 6. In addition, under a given constraint on the cardinality of the maximal clique, we search for distance graphs with extremal large values of the chromatic number. The resulting estimates are best possible within the framework of the proposed method, which combines probabilistic techniques with the linear-algebraic approach.     

Domination number of cubic graphs with large girth

We show that every n‐vertex cubic graph with girth at least g have domination number at most 0.299871n+ O(n/g)<3n/10 + O(n/g) which improves a previous bound of 0.321216n+ O(n/g) by Rautenbach and Reed. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:131‐142, 2012     

Edge intersection graphs of systems of paths on a grid with a bounded number of bends

We answer some of the questions raised by Golumbic, Lipshteyn and Stern and obtain some other results about edge intersection graphs of paths on a grid (EPG graphs). We show that for any d≥4, in order to represent every n vertex graph with maximum degree d as an edge intersection graph of n paths on a grid, a grid of area Θ(n²) is needed. We also show several results related to the classes B_k-EPG, where B_k-EPG denotes the class of graphs that have an EPG representation such that each path has at most k bends. In particular, we prove: For a fixed k and a sufficiently large n, the complete bipartite graph K_m,n does not belong to B_2m−3-EPG (it is known that this graph belongs to B_2m−2-EPG); for any odd integer k we have B_k-EPG B_k+1-EPG; there is no number k such that all graphs belong to B_k-EPG; only 2^O(knlog(kn)) out of all the labeled graphs with n vertices are in B_k-EPG.     

On rank three graphs with a large eigenvalue

Suppose a rank three graph has parameters n, k, λ, μ, and eigenvalues k, s, ?r. Assume that s is larger than a certain function of μ and r and that the graph has a rank three permutation group acting on it; then the graph is a partial geometry. This supplements a theorem of R.C. Bose.     

On infinite graphs with a specified number of colorings

In this paper we construct a planar graph of degree four which admits exactly N_u 3-colorings, we prove that such a graph must have degree at least four, and we consider various generalizations. We first allow our graph to have either one or two vertices of infinite degree and/or to admit only finitely many colorings and we note how this effects the degrees of the remaining vertices. We next consider n-colorings for n>3, and we construct graphs which we conjecture (but cannot prove) are of minimal degree. Finally, we consider nondenumerable graphs, and for every 3 <n<ω and every infinite cardinal k we construct a graph of cardinality k which admits exactly kn-colorings. We also show that the number of n-colorings of a denumerable graph can never be strictly between N_u and 2^N_u and that an appropriate generalization holds for at least certain nondenumerable 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.