A note on fragments of infinite graphs

Results involving automorphisms and fragments of infinite graphs are proved. In particular for a given fragmentC and a vertex-transitive subgroupG of the automorphism group of a connected graph there exists σ≠G such that σ[C] ⊂C. This proves the countable case of a conjecture of L. Babai and M. E. Watkins concerning graphs allowing a vertex-transitive torsion group action. Dedicated to Prof. K. Wagner on his 70^th birthday     

Classifying vertex-transitive graphs whose order is a product of two primes

Vertex-transitive graphs whose order is a product of two primes with a primitive automorphism group containing no imprimitive subgroup are classified. Combined with the results of [15] a complete classification of all vertex-transitive graphs whose order is a product of two primes is thus obtained (Theorem 2.1).Supported in part by the Research Council of SloveniaSupported in part by the Italian Ministry of Research (MURST)     

The connectivities of locally finite primitive graphs

Let be an infinite, locally finite graph whose automorphism group is primitive on its vertex set. It is shown that the connectivity of cannot equal 2, but all other values 0, 1, 3, 4, ... are possible.     

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).     

An infinite family of tetravalent half-arc-transitive graphs

A graph is half-arc-transitive if its automorphism group acts transitively on vertices and edges, but not on arcs. In this paper, a new infinite family of tetravalent half-arc-transitive graphs with girth 4 is constructed, each of which has order 16m such that m>1 is a divisor of 2t²+2t+1 for a positive integer t and is tightly attached with attachment number 4m. The smallest graph in the family has order 80.     

On the Hadwiger number of infinite graphs

LetX be a connected graph with bounded valency and at least one thick end. We show that the existence of certain subgroups of the automorphism group ofX always implies thatX has infinite Hadwiger number.     

A new bound for neighbor-connectivity of abelian Cayley graphs

For the notion of neighbor-connectivity in graphs, whenever a vertex is “subverted” the entire closed neighborhood of the vertex is deleted from the graph. The minimum number of vertices whose subversion results in an empty, complete, or disconnected subgraph is called the neighbor-connectivity of the graph. Gunther, Hartnell, and Nowakowski have shown that for any graph, neighbor-connectivity is bounded above by κ. The main result of this paper is a sharpening of the bound for abelian Cayley graphs. In particular, we show by constructing an effective subversion strategy for such graphs, that neighbor-connectivity is bounded above by ⌈δ/2⌉+2. Using a result of Watkins the new bound can be recast in terms of κ to get neighbor-connectivity bounded above by ⌈3κ/4⌉+2 for abelian Cayley graphs.     

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.     

Additivity of the crossing number of graphs with connectivity 2

We prove that the crossing number of graphs with connectivity 2 has in certain cases an additive property analogous to that of crossing number of graphs with connectivity ≤1.     

The cover pebbling number of graphs

A pebbling move on a graph consists of taking two pebbles off of one vertex and placing one pebble on an adjacent vertex. In the traditional pebbling problem we try to reach a specified vertex of the graph by a sequence of pebbling moves. In this paper we investigate the case when every vertex of the graph must end up with at least one pebble after a series of pebbling moves. The cover pebbling number of a graph is the minimum number of pebbles such that however the pebbles are initially placed on the vertices of the graph we can eventually put a pebble on every vertex simultaneously. We find the cover pebbling numbers of trees and some other graphs. We also consider the more general problem where (possibly different) given numbers of pebbles are required for the vertices.     

The cover-index of infinite graphs

We show that the cover-index of an infinite graph can be expressed in terms of colouring properties of its finite subgraphs when the minimum degree of the graph is finite. We prove that every simple graph with infinite minimum degree contains a tree which is regular of degree and use this to prove that every graph with minimum degree can be decomposed into mutually edge-disjoint spanning subgraphs without ioslated vertices. In particular, the cover-index of a graph equals the minimum degree, when this is infinite.     

Independence and coloring properties of direct products of some vertex-transitive graphs

Let α(G) and χ(G) denote the independence number and chromatic number of a graph G, respectively. Let G×H be the direct product graph of graphs G and H. We show that if G and H are circular graphs, Kneser graphs, or powers of cycles, then α(G×H)=max{α(G)|V(H)|,α(H)|V(G)|} and χ(G×H)=min{χ(G),χ(H)}.     

The complexity of a class of infinite graphs

IfG _k is the family of countable graphs with nok vertex (or edge) disjoint circuits (1<k<) then there is a countableG _k G _k such that every member ofG _k is an (induced) subgraph of some member ofG _k , but no finiteG _k suffices.     

Optimal tristance anticodes in certain graphs

For z₁,z₂,z₃∈Zⁿ, the tristance d₃(z₁,z₂,z₃) is a generalization of the L₁-distance on Zⁿ to a quantity that reflects the relative dispersion of three points rather than two. A tristance anticodeA_d of diameter d is a subset of Zⁿ with the property that d₃(z₁,z₂,z₃)?d for all z₁,z₂,z₃∈A_d. An anticode is optimal if it has the largest possible cardinality for its diameter d. We determine the cardinality and completely classify the optimal tristance anticodes in Z² for all diameters d?1. We then generalize this result to two related distance models: a different distance structure on Z² where d(z₁,z₂)=1 if z₁,z₂ are adjacent either horizontally, vertically, or diagonally, and the distance structure obtained when Z² is replaced by the hexagonal lattice A₂. We also investigate optimal tristance anticodes in Z³ and optimal quadristance anticodes in Z², and provide bounds on their cardinality. We conclude with a brief discussion of the applications of our results to multi-dimensional interleaving schemes and to connectivity loci in the game of Go.     

On 3-pushdown graphs with large separators

For an integers letl ^s (n), thes-iterated logarithm function, be defined inductively:l ⁰ (n)=n,l ^s+1 (n)=log₂ (l ² (n)) fors0. We show that for every fixeds and alln large enough, there is ann-vertex 3-pushdown graph whose smallest separator contains at least(n/l ^s (n)) vertices.The work of the first author was supported in part by NSF Grants MCS-83-03139, DCR-85-11713 and CCR-86-05353.The work of the second author was supported in part by NSF Grants MCS-84-16190.     

The sextet construction for cubic graphs

We show how to construct cubic graphs which have automorphism groups acting regularly on thes-arcs,s=4 or 5.     

The choice number of random bipartite graphs

A random bipartite graphG(n, n, p) is obtained by taking two disjoint subsets of verticesA andB of cardinalityn each, and by connecting each pair of verticesaA andbB by an edge randomly and independently with probabilityp=p(n). We show that the choice number ofG(n, n, p) is, almost surely, (1+o(1))log₂(np) for all values of the edge probabilityp=p(n), where theo(1) term tends to 0 asnp tends to infinity.Research supported in part by a USA-Israeli BSF grant, a grant from the Israel Science Foundation, a Sloan Foundation grant No. 96-6-2 and a State of New Jersey grant.Research supported by an IAS/DIMACS Postdoctoral Fellowship.     

The forcing number of graphs with given girth

In this paper, we study a dynamic coloring of the vertices of a graph G that starts with an initial subset S of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set S is called a forcing set of G if, by iteratively applying the forcing process, every vertex in G becomes colored. The forcing number, originally known as the zero forcing number, and denoted F (G), of G is the cardinality of a smallest forcing set of G. We study lower bounds on the forcing number in terms of its minimum degree and girth, where the girth g of a graph is the length of a shortest cycle in the graph. Let G be a graph with minimum degree δ ≥ 2 and girth g ≥ 3. Davila and Kenter [Theory and Applications of Graphs, Volume 2, Issue 2, Article 1, 2015] conjecture that F (G) ≥ δ + (δ ? 2)(g ? 3). This conjecture has recently been proven for g ≤ 6. The conjecture is also proven when the girth g ≥ 7 and the minimum degree is sufficiently large. In particular, it holds when g = 7 and δ ≥ 481, when g = 8 and δ ≥ 649, when g = 9 and δ ≥ 30, and when g = 10 and δ ≥ 34. In this paper, we prove the conjecture for g ∈ {7, 8, 9, 10} and for all values of δ ≥ 2.     

Girths of bipartite sextet graphs

An explicit construction of Biggs and Hoare yields an infinite family of bipartite cubic graphs. We prove that the ordern and girthg of each of these graphs are related by log₂ n<3/4·g+3/2.     

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.