Maximum set of edges no two covered by a clique

Leth(G) be the largest number of edges of the graphG. no two of which are contained in the same clique. ForG without isolated vertices it is proved that ifh(G)≦5, thenχ( )≦h(G), but ifh(G)=6 thenχ( ) can be arbitrarily large.     

Eliminating graphs by means of parallel knock-out schemes

In 1997 Lampert and Slater introduced parallel knock-out schemes, an iterative process on graphs that goes through several rounds. In each round of this process, every vertex eliminates exactly one of its neighbors. The parallel knock-out number of a graph is the minimum number of rounds after which all vertices have been eliminated (if possible). The parallel knock-out number is related to well-known concepts like perfect matchings, hamiltonian cycles, and 2-factors.We derive a number of combinatorial and algorithmic results on parallel knock-out numbers: for families of sparse graphs (like planar graphs or graphs of bounded tree-width), the parallel knock-out number grows at most logarithmically with the number n of vertices; this bound is basically tight for trees. Furthermore, there is a family of bipartite graphs for which the parallel knock-out number grows proportionally to the square root of n. We characterize trees with parallel knock-out number at most 2, and we show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach (whereas in general graphs this problem is known to be NP-hard). Finally, we prove that the parallel knock-out number of a claw-free graph is either infinite or less than or equal to 2.     

Contractible edges in triangle-free graphs

An edge of a graph is calledk-contractible if the contraction of the edge results in ak-connected graph. Thomassen [5] proved that everyk-connected graph of girth at least four has ak-contractible edge. In this paper, we study the distribution ofk-contractible edges in triangle-free graphs and show the following: Whenk≧2, everyk-connected graph of girth at least four and ordern≧3k, hasn+(3/2)k ²-3k or morek-contractible edges.     

On the minimal number of edges in color-critical graphs

A graphG isk-critical if it has chromatic numberk, but every proper subgraph of it is (k?1)-colorable. This paper is devoted to investigating the following question: for givenk andn, what is the minimal number of edges in ak-critical graph onn vertices, with possibly some additional restrictions imposed? Our main result is that for everyk≥4 andn>k this number is at least $\left( {\frac{{k - 1}}{2} + \frac{{k - 3}}{{2(k^2 - 2k - 1)}}} \right)n$ , thus improving a result of Gallai from 1963. We discuss also the upper bounds on the minimal number of edges ink-critical graphs and provide some constructions of sparsek-critical graphs. A few applications of the results to Ramsey-type problems and problems about random graphs are described.     

Quasi-planar graphs have a linear number of edges

A graph is calledquasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph withn vertices isO(n).Work on this paper by Pankaj K. Agarwal, Boris Aronov and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work on this paper by Pankaj K. Agarwal has also been supported by NSF Grant CCR-93-01259, by an Army Research Office MURI grant DAAH04-96-1-0013, by an NYI award, and by matching funds from Xerox Corporation. Work on this paper by Boris Aronov has also been supported by NSF Grant CCR-92-11541 and by a Sloan Research Fellowship. Work on this paper by János Pach, Richard Pollack, and Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-94-24398. Work by János Pach was also supported by Grant OTKA-4269 and by a CUNY Research Award. Work by Richard Pollack was also supported by NSF Grants CCR-94-02640 and DMS-94-00293. Work by Micha Sharir was also supported by NSF Grant CCR-93-11127, by a Max-Planck Research Award, and by grants from the Israel Science Fund administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. Part of the work on this paper was done during the participation of the first four authors in the Special Semester on Computational and Combinatorial Geometry organized by the Mathematical Research Institute of Tel Aviv University, Spring 1995.     

On automorphisms of infinite graphs with forbidden subgraphs

LexX be anm-connected infinite graph without subgraphs homeomorphic toKm, n, for somen, and let α be an automorphism ofX with at least one cycle of infinite length. We characterize the structure of α and use this characterization to extend a known result about orientation-preserving automorphisms of finite plane graphs to infinite plane graphs. In the last section we investigate the action of α on the ends ofX and show that α fixes at most two ends (Theorem 3.2).     

Contractions of graphs with no spanning eulerian subgraphs

Letp2 be a fixed integer, and letG be a connected graph onn vertices. If(G)2, ifd(u)+d(v)>2n/p–2 holds wheneveruvE(G), and ifn is sufficiently large compared top, then eitherG has a spanning eulerian subgraph, orG is contractible to a graphG ₁ of order less thenp and with no spanning eulerian subgraph. The casep=2 was proved by Lesniak-Foster and Williamson. The casep=5 was conjectured by Benhocine, Clark, Köhler, and Veldman, when they proved virtually the casep=3. The inequality is best-possible.     

H-extension of graphs

We consider the problem of constructing a graphG* from a collection of isomorphic copies of a graphG in such a way that for every two copies ofG, either no vertices or a section graph isomorphic to a graphH is identified. It is shown that ifG can be partitioned into vertex-disjoint copies ofH, thenG* can be made to have at most |H| orbits. A condition onG so thatG* can be vertextransitive is also included.     

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.     

Semimodular lattices with isomorphic graphs

Two discrete modular lattice and have isomorphic graphs if and only if is of the form A × and is of the form A × for some lattices A and and . We prove that for discrete semimodular lattices and this latter condition holds if and only if and have isomorphic graphs and the isomorphism preserves the order on all cover-preserving sublattices of which are isomorphic to the seven-element, semimodular, nonmodular lattice (see Figure 1). This answers in the affirmative a question posed by J. Jakubik.     

Unicyclic graphs with large energy

We study the energy (i.e., the sum of the absolute values of all eigenvalues) of so-called tadpole graphs, which are obtained by joining a vertex of a cycle to one of the ends of a path. By means of the Coulson integral formula and careful estimation of the resulting integrals, we prove two conjectures on the largest and second-largest energy of a unicyclic graph due to Caporossi, Cvetkovi?, Gutman and Hansen and Gutman, Furtula and Hua, respectively. Moreover, we characterise the non-bipartite unicyclic graphs whose energy is largest.     

Posets with interval upper bound graphs

Competition graphs of transitive acyclic digraphs are strict upper bound graphs. This paper characterizes those posets, which can be considered transitive acyclic digraphs, which have upper bound graphs that are interval graphs. The results proved here may shed some light on the open question of those digraphs which have interval competition graphs.This material is taken from Chapter 3 of my (maiden name Diny) PhD Dissertation.     

Hamiltonian paths with prescribed edges in hypercubes

Given a set P of at most 2n-4 prescribed edges (n?5) and vertices u and v whose mutual distance is odd, the n-dimensional hypercube Q_n contains a hamiltonian path between u and v passing through all edges of P iff the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as endvertices. This resolves a problem of Caha and Koubek who showed that for any n?3 there exist vertices u,v and 2n-3 edges of Q_n not contained in any hamiltonian path between u and v, but still satisfying the condition above. The proof of the main theorem is based on an inductive construction whose basis for n=5 was verified by a computer search. Classical results on hamiltonian edge-fault tolerance of hypercubes are obtained as a corollary.     

Minimal non-1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge. A non-1-planar graph G is minimal if the graph G-e is 1-planar for every edge e of G. We prove that there are infinitely many minimal non-1-planar graphs (MN-graphs). It is known that every 6-vertex graph is 1-planar. We show that the graph K₇-K₃ is the unique 7-vertex MN-graph.     

Some graphs with small second eigenvalue

For any prime,p, we construct a Cayley graph on the group,G, of affine linear transformations ofℤ/pℤ of degree 2(p−1) and second eigenvalue with the following special property: the adjacency matrix of the graph is supported on the “blocks” associated to the trivial representation and the irreducible representation of sizep−1. SinceG is of orderp(p−1), the correspondingt-uniform Cayley hypergraph has essentially optimal second eigenvalue for this degree and size of the graph (see [2] for definitions). En route we give, for any integerk>1, a simple Cayley graph onp ^k nodes of degreep of second eigenvalue . The author wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR-8858788, and the Office of Naval Research under Grant N00014-87-K-0467.     

On well-quasi-ordering-finite graphs by immersion

It has been conjectured by Nash-Williams that the class of all graphs is well-quasi-ordered under the quasi-order ≦ defined by immersion. Two partial results are proved which support this conjecture. (i) The class of finite simple graphsG with K _2,3 is well-quasi-ordered by ≦, (ii) it is shown that a class of finite graphs is well-quasi-ordered by ≦ provided that the blocks of its members satisfy certain restrictive conditions. (In particular, this second result implies that ≦ is a well-quasi-order on the class of graphs for which each block is either complete or a cycle.)     

On digraphs with no two disjoint directed cycles

We obtain a result on configurations in 2-connected digraphs with no two disjoint dicycles. We derive various consequences, for example a short proof of the characterization of the minimal digraphs having no vertex meeting all dicycles and a polynomially bounded algorithm for finding a dicycle through any pair of prescribed arcs in a digraph with no two disjoint dicycles, a problem which is NP-complete for digraphs in general.     

Packing paths in planar graphs

A generalization of P. Seymour's theorem on planar integral 2-commodity flows is given when the underlying graphG together with the demand graphH (a graph having edges that connect the corresponding terminal pairs) form a planar graph and the demand edges are on two faces ofG.     

Regular odd rings and non-planar graphs

In a previous paper we have announced that a graph is non-planar if and only if it contains a maximal, strict, compact, odd ring. Little has conjectured that the compactness condition may be removed. Chernyak has now published a proof of this conjecture. However, it is difficult to test a ring for maximality. In this paper we show that for odd rings of size five or greater, the condition of maximality may be replaced by a new one called regularity. Regularity is an easier condition to diagnose than is maximality.     

Nonexistence of universal graphs without some trees

IfG is a finite tree with a unique vertex of largest, and 4 degree which is adjacent to a leaf then there is no universal countableG-free graph.Research partially supported by the Hungarian Science Research Grant OTKA No. 2117 and by the European Communities (Cooperation in Science and Technology with Central and Eastern European Countries) contract number ERBCIPACT930113.