Partition graphs for finite symmetric groups

This paper outlines an investigation of a class of arc-transitive graphs admitting a finite symmetric group S_n acting primitively on vertices, with vertex-stabilizer isomorphic to the wreath product S_m wr S_r (preserving a partition of {1,2,…n} into r parts of equal size m). Several properties of these graphs are considered, including their correspondence with r × r matrices with constant row- and column-sums equal to m, their girth, and the local action of the vertex-stabilizer. Also, it is shown that the only instance where S_n acts transitively on 2-arcs occurs in the case m = r = 2. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 107–117, 1997     

Invariant boundary distributions for finite graphs

Let Γ be the fundamental group of a finite connected graph G. Let M be an abelian group. A distribution on the boundary ∂Δ of the universal covering tree Δ is an M-valued measure defined on clopen sets. If M has no χ(G)-torsion, then the group of Γ-invariant distributions on ∂Δ is isomorphic to H₁(G,M).     

The reconstruction conjecture for finite simple graphs and associated directed graphs

In this paper, we study the Reconstruction Conjecture for finite simple graphs. Let Γ and ${\mathrm{\Gamma }}^{\prime }$ be finite simple graphs with at least three vertices such that there exists a bijective map $f:V(\mathrm{\Gamma })\to V({\mathrm{\Gamma }}^{\prime })$ and for any $v\in V(\mathrm{\Gamma })$, there exists an isomorphism ${?}_v:\mathrm{\Gamma }?v\to {\mathrm{\Gamma }}^{\prime }?f(v)$. Then we define the associated directed graph $\stackrel{?}{\mathrm{\Gamma }}=\stackrel{?}{\mathrm{\Gamma }}(\mathrm{\Gamma },{\mathrm{\Gamma }}^{\prime },f,{\{{?}_v\}}_{v\in V(\mathrm{\Gamma })})$ with two kinds of arrows from the graphs Γ and ${\mathrm{\Gamma }}^{\prime }$, the bijective map f and the isomorphisms ${\{{?}_v\}}_{v\in V(\mathrm{\Gamma })}$. By investigating the associated directed graph $\stackrel{?}{\mathrm{\Gamma }}$, we study when are the two graphs Γ and ${\mathrm{\Gamma }}^{\prime }$ isomorphic.     

An edge-deletion problem for locally finite graphs

For each positive integer n, let T_n be the tree in which exactly one vertex has degree n and all the other vertices have degree n + 1. A graph G is called stable if its edge set is nonempty and if deleting an arbitrary edge of G there is always a component of the residue graph which is isomorphic to G. The question whether there are locally finite stable graphs that are not isomorphic to one of the graphs T_n is answered affirmatively by constructing an uncountable family of pairwise nonisomorphic, locally finite, stable graphs. Further, the following results are proved: (1) Among the locally finite trees containing no subdivision of T₂, the oneway infinite path T₁ is the only stable graph. (2) Among the locally finite graphs containing no two-way infinite path, T₁ is also the only stable graph.     

Locally finite homogeneous graphs

A connected graph G is said to be z-homogeneous if any isomorphism between finite connected induced subgraphs of G extends to an automorphism of G. Finite z-homogeneous graphs were classified in [17]. We show that z-homogeneity is equivalent to finite-transitivity on the class of infinite locally finite graphs. Moreover, we classify the graphs satisfying these properties. Our study of bipartite z-homogeneous graphs leads to a new characterization for hypercubes.     

Invariants of finite comparability graphs

We study some invariants of finite comparability graphs. This research was supported by the NSERC of Canada.     

Isomorphisms of finite semi-Cayley graphs

Let G be a finite group. A Cayley graph over G is a simple graph whose automorphism group has a regular subgroup isomorphic to G. A Cayley graph is called a CI-graph(Cayley isomorphism) if its isomorphic images are induced by automorphisms of G. A well-known result of Babai states that a Cayley graph Γ of G is a CI-graph if and only if all regular subgroups of Aut(Γ) isomorphic to G are conjugate in Aut(Γ). A semi-Cayley graph(also called bi-Cayley graph by some authors) over G is a simple graph whose automorphism group has a semiregular subgroup isomorphic to G with two orbits(of equal size). In this paper, we introduce the concept of SCI-graph(semi-Cayley isomorphism)and prove a Babai type theorem for semi-Cayley graphs. We prove that every semi-Cayley graph of a finite group G is an SCI-graph if and only if G is cyclic of order 3. Also, we study the isomorphism problem of a special class of semi-Cayley graphs.     

Signless Laplacians of finite graphs

We survey properties of spectra of signless Laplacians of graphs and discuss possibilities for developing a spectral theory of graphs based on this matrix. For regular graphs the whole existing theory of spectra of the adjacency matrix and of the Laplacian matrix transfers directly to the signless Laplacian, and so we consider arbitrary graphs with special emphasis on the non-regular case. The results which we survey (old and new) are of two types: (a) results obtained by applying to the signless Laplacian the same reasoning as for corresponding results concerning the adjacency matrix, (b) results obtained indirectly via line graphs. Among other things, we present eigenvalue bounds for several graph invariants, an interpretation of the coefficients of the characteristic polynomial, a theorem on powers of the signless Laplacian and some remarks on star complements.     

The finite edge-primitive pentavalent graphs

A graph is edge-primitive if its automorphism group acts primitively on edges. Weiss (in J. Comb. Theory Ser. B 15, 269–288, 1973) determined edge-primitive cubic graphs. In this paper, we classify edge-primitive pentavalent graphs. The same classification of those of valency 4 is also done.     

Embedding finite graphs into graphs colored with infinitely many colors

We prove that for any cardinalτ and for any finite graphH there is a graphG such that for any coloring of the pairs of vertices ofG withτ colors there is always a copy ofH which is an induced subgraph ofG so that both the edges of the copy and the edges of the complement of the copy are monochromatic. Research supported by Hungarian National Science Foundation OTKA grant 1805.     

Embedding arbitrary finite simple graphs into small strongly regular graphs

It is well known that any finite simple graph Γ is an induced subgraph of some exponentially larger strongly regular graph Γ (e.g., [2, 8]). No general polynomial‐size construction has been known. For a given finite simple graph Γ on υ vertices, we present a construction of a strongly regular graph Γ on O(υ⁴) vertices that contains Γ as its induced subgraph. A discussion is included of the size of the smallest possible strongly regular graph with this property. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 1–8, 2000     

Branching graphs for finite unitary groups in nondefining characteristic

We show that the modular branching rule (in the sense of Harish-Chandra) on unipotent modules for finite unitary groups is piecewise described by particular connected components of the crystal graph of well-chosen Fock spaces, under favorable conditions. Besides, we give the combinatorial formula to pass from one to the other in the case of modules arising from cuspidal modules of defect 0. This partly proves a recent conjecture of Jacon and the authors.     

Duality theorems for regular homotopy of finite directed graphs

Dati uno spazio topologico normale e numerabilmente paracompattoS ed un grafo finito ed orientatoG si prova che tra gli insiemiQ(S, G) eQ ^*(S, G) delle classi dio-omotopia e dio ^*-omotopia esiste una biiezione naturale. Nelle stesse condizioni, seS′ è un sottospazio chiuso diS eG′ un sottografo diG, esiste ancora una biiezione naturale tra gli insiemiQ (S, S′; G, G′) eQ ^* (S, S′; G, G′) delle classi di omotopia. Si mostra infine che in condizioni meno restrittive per lo spazioS le precedenti biiezioni possono non sussistere.     

Dirichlet problem on locally finite graphs

In this paper, we study the existence and uniqueness of solutions to the vertex-weighted Dirichlet problem on locally finite graphs. Let B be a subset of the vertices of a graph G. The Dirichlet problem is to find a function whose discrete Laplacian on G?B and its values on B are given. Each infinite connected component of G?B is called an end of G relative to B. If there are no ends, then there is a unique solution to the Dirichlet problem. Such a solution can be obtained as a limit of an averaging process or as a minimizer of a certain functional or as a limit-solution of the heat equation on the graph. On the other hand, we show that if G is a locally finite graph with l ends, then the set of solutions of any Dirichlet problem, if non-empty, is at least l-dimensional.