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

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.     

Extending partial isomorphisms of graphs

Theorem Let X be a finite graph. Then there exists a finite graph Z containing X as an induced subgraphs, such that every isomorphism between induced subgraphs of X extends to an automorphism of Z.The graphZ may be required to be edge-transitive. The result implies that for anyn, there exists a notion of a genericn-tuple of automorphism of the Rado graphR (the random countable graph): for almost all automorphism ₁,..., _n and ₁ ofR (in the sense of Baire category), (R,₁,..., _n ), (R,₁,..., _n ). The problem arose in a recent paper of Hodges, Hodgkinson, Lascar and Shelah, where the theorem is used to prove the small index property forR.Work supported by a Sloan Fellowship and by NSF grant DMS-8903378.     

On pallets for Fox colorings of spatial graphs

We introduce the notion of pallets of quandles and define coloring invariants for spatial graphs which give a generalization of Fox colorings studied in Ishii and Yasuhara (1997) [4]. All pallets for dihedral quandles are obtained from the quotient sets of the universal pallets under a certain equivalence relation. We study the quotient sets and classify their elements.     

Semisymmetric graphs

Let be a regular covering projection of connected graphs with the group of covering transformations isomorphic to N. If N is an elementary abelian p-group, then the projection ℘_N is called p-elementary abelian. The projection ℘_N is vertex-transitive (edge-transitive) if some vertex-transitive (edge-transitive) subgroup of the automorphism group of X lifts along ℘_N, and semisymmetric if it is edge- but not vertex-transitive. The projection ℘_N is minimal semisymmetric if it cannot be written as a composition ℘_N=℘℘_M of two (nontrivial) regular covering projections, where ℘_M is semisymmetric.Malni? et al. [Semisymmetric elementary abelian covers of the Möbius-Kantor graph, Discrete Math. 307 (2007) 2156-2175] determined all pairwise nonisomorphic minimal semisymmetric elementary abelian regular covering projections of the Möbius-Kantor graph, the Generalized Petersen graph GP(8,3), by explicitly giving the corresponding voltage rules generating the covering projections. It was remarked at the end of the above paper that the covering graphs arising from these covering projections need not themselves be semisymmetric (a graph with regular valency is said to be semisymmetric if its automorphism group is edge- but not vertex-transitive). In this paper it is shown that all these covering graphs are indeed semisymmetric.     

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     

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.     

Energy of unitary Cayley graphs and gcd-graphs

This work is based on ideas of Ili? [A. Ili?, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009) 1881-1889] on the energy of unitary Cayley graph. For a finite commutative ring R with unity , the unitary Cayley graph of R is the Cayley graph whose vertex set is R and the edge set is {{a,b}:a,b∈Randa-b∈R^×}, where R^× is the group of units of R. We study the eigenvalues of the unitary Cayley graph of a finite commutative ring and some gcd-graphs and compute their energy. Moreover, we obtain the energy for the complement of unitary Cayley graphs.     

Minimal generators of toric ideals of graphs

Let IG be the toric ideal of a graph G. We characterize in graph theoretical terms the primitive, the minimal, the indispensable and the fundamental binomials of the toric ideal IG.     

Infinite distance transitive graphs of finite valency

We determine all infinite distance transitive graphs of finite valency, thereby proving a conjecture of C. D. Godsil. The proof makes heavy use of a theorem of M. J. Dunwoody concerning cuts of infinite graphs. In section 1 there is a rough analysis of the appearance of such graphs, and in section 2 we state and apply Dunwoody’s theorem. The proof is completed in section 3.     

The Hadwiger number of infinite vertex-transitive graphs

We prove that every infinite, locally finite 3-connected, almost 4-connected, almost transitive, nonplanar graph, which contains infinitely many pairwise disjoint infinite paths belonging to the same end, can be contracted into an infinite complete graph. This implies that every infinite, locally finite, connected, nonplanar vertex-transitive graph with only one end can be contracted into an infinite complete graph. This problem was raised by L. Babai.     

Cyclotomic graphs and perfect codes

We study two families of cyclotomic graphs and perfect codes in them. They are Cayley graphs on the additive group of $\mathbb{Z}[{\zeta }_m]/A$, with connection sets $\{\pm ({\zeta }_m^i+A):0\le i\le m?1\}$ and $\{\pm ({\zeta }_m^i+A):0\le i\le ?(m)?1\}$, respectively, where ${\zeta }_m$ ($m\ge 2$) is an mth primitive root of unity, A a nonzero ideal of $\mathbb{Z}[{\zeta }_m]$, and ? Euler's totient function. We call them the mth cyclotomic graph and the second kind mth cyclotomic graph, and denote them by $G_m(A)$ and $G_m^{?}(A)$, respectively. We give a necessary and sufficient condition for $D/A$ to be a perfect t-code in $G_m^{?}(A)$ and a necessary condition for $D/A$ to be such a code in $G_m(A)$, where $t\ge 1$ is an integer and D an ideal of $\mathbb{Z}[{\zeta }_m]$ containing A. In the case when $m=3,4$, $G_m((\alpha ))$ is known as an Eisenstein–Jacobi and Gaussian networks, respectively, and we obtain necessary conditions for $(\beta )/(\alpha )$ to be a perfect t-code in $G_m((\alpha ))$, where $0\ne \alpha ,\beta \in \mathbb{Z}[{\zeta }_m]$ with β dividing α. In the literature such conditions are known to be sufficient when $m=4$ and $m=3$ under an additional condition. We give a classification of all first kind Frobenius circulants of valency 2p and prove that they are all pth cyclotomic graphs, where p is an odd prime. Such graphs belong to a large family of Cayley graphs that are efficient for routing and gossiping.     

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.     

Cutting up graphs

LetΓ be infinite connected graph with more than one end. It is shown that there is a subsetd ⊂V Γ which has the following properties. (i) Bothd andd*=VΓ\d are infinite. (ii) there are only finitely many edges joiningd andd*. (iii) For eachgε AutΓ at least one ofd⊂dg, d*⊂dg, d⊂d* g, d*⊂d* g holds. Any group acting on Γ has a decomposition as a free product with amalgamation or as an HNN-group.     

Paired domination on interval and circular-arc graphs

We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O(m+n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O(m(m+n)) time.     

On a pursuit game on cayley graphs

The game cops and robbers is considered on Cayley graphs of abelian groups. It is proved that if the graph has degreed, then [(d+1)/2] cops are sufficient to catch one robber. This bound is often best possible.     

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.     

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.     

Automorphism groups of comparability and covering graphs

Let G be a group and H a subgroup of G. It is shown that there exists a partially ordered set (X, ) such that G is isomorphic to the group of all automorphisms of the comparability graph of (X, ) and such that under this isomorphism H is mapped onto the group of all order-automorphisms of (X, ). There also exists a partially ordered set (Y, ) such that G is isomorphic to the group of all automorphisms of the covering graph of (Y, ) and such that under this isomorphism H is mapped onto the group of all order-automorphisms of (Y, ). In this representation X and Y can be taken to be finite if G is finite and of the same cardinality as G if G is infinite.     

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.