Direct products of automorphism groups of graphs

In this article we study the product action of the direct product of automorphism groups of graphs. We generalize the results of Watkins [J. Combin Theory 11 (1971), 95–104], Nowitz and Watkins [Monatsh. Math. 76 (1972), 168–171] and W. Imrich [Israel J. Math. 11 (1972), 258–264], and we show that except for an infinite family of groups S_n × S_n, n≥2 and three other groups D₄ × S₂, D₄ × D₄ and S₄ × S₂ × S₂, the direct product of automorphism groups of two graphs is itself the automorphism group of a graph. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 26–36, 2009     

Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps

This paper deals with the Cayley graph $\mathrm{Cay}({\mathrm{Sym}}_n,T_n)$, where the generating set consists of all block transpositions. A motivation for the study of these particular Cayley graphs comes from current research in Bioinformatics. As the main result, we prove that $\text{Aut}\left(\mathrm{Cay}({\mathrm{Sym}}_n,T_n)\right)$ is the product of the left translation group and a dihedral group ${\mathsf{D}}_{n+1}$ of order $2(n+1)$. The proof uses several properties of the subgraph $\Gamma$ of $\mathrm{Cay}({\mathrm{Sym}}_n,T_n)$ induced by the set $T_n$. In particular, $\Gamma$ is a $2(n?2)$-regular graph whose automorphism group is ${\mathsf{D}}_{n+1},$ $\Gamma$ has as many as $n+1$ maximal cliques of size $2$, and its subgraph $\Gamma \left(V\right)$ whose vertices are those in these cliques is a 3-regular, Hamiltonian, and vertex-transitive graph. A relation of the unique cyclic subgroup of ${\mathsf{D}}_{n+1}$ of order $n+1$ with regular Cayley maps on ${\text{Sym}}_n$ is also discussed. It is shown that the product of the left translation group and the latter group can be obtained as the automorphism group of a non-$t$-balanced regular Cayley map on ${\text{Sym}}_n$.     

Commuting decompositions of complete graphs

We say that two graphs G and H with the same vertex set commute if their adjacency matrices commute. In this article, we show that for any natural number r, the complete multigraph K is decomposable into commuting perfect matchings if and only if n is a 2‐power. Also, it is shown that the complete graph K_n is decomposable into commuting Hamilton cycles if and only if n is a prime number. © 2006 Wiley Periodicals, Inc. J Combin Designs     

Structure of a Conjugating Automorphism Group

We examine the automorphism group Aut(F _n ) of a free group F _n of rank n 2 on free generators x ₁, x ₂,...,x _n . It is known that Aut(F ₂) can be built from cyclic subgroups using a free and semidirect product. A question remains open as to whether this result can be extended to the case n > 2. Every automorphism of Aut(F _n ) sending a generator x _i to an element f _i ^-1 x _(i) f _i , where f _i F _n and is some permutation on a symmetric group S _n , is called a conjugating automorphism. The conjugating automorphism group is denoted C _n . A set of automorphisms for which is the identity permutation form a basis-conjugating automorphism group, denoted Cb _n . It is proved that Cb _n can be factored into a semidirect product of some groups. As a consequence we obtain a normal form for words in C _n . For n 4, C _n and Cb _n have an undecidable occurrence problem in finitely generated subgroups. It is also shown that C _n , n 2, is generated by at most four elements, and we find its respective genetic code, and that Cb _n , n 2, has no proper verbal subgroups of finite width.     

The Spectrum and Automorphism Group of the Set-Inclusion Graph

Let n,k and l be integers with 1 ≤ k ＜ l ≤ n-1.The set-inclusion graph G(n,k,l) is the graph whose vertex set consists of all k-andl-subsets of[n]={1,2,...,n},where two distinct vertices are adjacent if one of them is contained in the other.In this paper,we determine the spectrum and automorphism group of G(n,k,l).     

Sandpile groups and the coeulerian property for random directed graphs

We consider random directed graphs, and calculate the distribution of the cokernels of their laplacian, following the methods used by Wood. As a corollary, we show that the probability that a random digraph is coeulerian is asymptotically upper bounded by a constant around 0.43.     

Adjacency matrices of probe interval graphs

In this paper we obtain several characterizations of the adjacency matrix of a probe interval graph. In course of this study we describe an easy method of obtaining interval representation of an interval bigraph from its adjacency matrix. Finally, we note that if we add a loop at every probe vertex of a probe interval graph, then the Ferrers dimension of the corresponding symmetric bipartite graph is at most 3.     

Bubble-sort图和Modified Bubble-sort图的自同构群

Bubble-Sort图和Modified Bubble-Sort图是两类特殊的Cayley图,由于其在网络构建中的应用而受到广泛关注.本文完全确定了这两类图的自同构群.     

Corrigendum: Combinatorial properties of integer matrices and integer matrices mod k

We correct an error in our paper “Combinatorial Properties of Integer Matrices and Integer Matrices mod k” that appeared in this journal (66, 1380–1402 (2017)).     

偶错位图的张量幂的最大独立集和自同构群

若A_n 是X := {1, 2,..., n} 上的偶置换构成的交错群, E_n 是X 上的偶错位集, 则Cayley 图AΓ_n := Γ(A_n, E_n) 称为偶错位图. 令AΓ_n^q 为q 个AΓ_n 的张量幂. 在本文中, 我们研究了AΓ_n^q 的连通性、直径、独立数、团数、色数和最大独立集等性质. 利用AΓ_n^q 最大独立集的结果, 我们完全确定了AΓ_n^q 的自同构群的结构.     

Non-Cayley Vertex-Transitive Graphs of Order Twice the Product of Two Odd Primes

For a positive integer n, does there exist a vertex-transitive graph Γ on n vertices which is not a Cayley graph, or, equivalently, a graph Γ on n vertices such that Aut Γ is transitive on vertices but none of its subgroups are regular on vertices? Previous work (by Alspach and Parsons, Frucht, Graver and Watkins, Marusic and Scapellato, and McKay and the second author) has produced answers to this question if n is prime, or divisible by the square of some prime, or if n is the product of two distinct primes. In this paper we consider the simplest unresolved case for even integers, namely for integers of the form n = 2pq, where 2 < q < p, and p and q are primes. We give a new construction of an infinite family of vertex-transitive graphs on 2pq vertices which are not Cayley graphs in the case where p ≡ 1 (mod q). Further, if p ? 1 (mod q), p ≡ q ≡ 3(mod 4), and if every vertex-transitive graph of order pq is a Cayley graph, then it is shown that, either 2pq = 66, or every vertex-transitive graph of order 2pq admitting a transitive imprimitive group of automorphisms is a Cayley graph.     

Sandpile groups and spanning trees of directed line graphs

We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph G and its directed line graph LG. The sandpile group is an abelian group associated to a directed graph, whose order is the number of oriented spanning trees rooted at a fixed vertex. In the case when G is regular of degree k, we show that the sandpile group of G is isomorphic to the quotient of the sandpile group of LG by its k-torsion subgroup. As a corollary we compute the sandpile groups of two families of graphs widely studied in computer science, the de Bruijn graphs and Kautz graphs.     

Geometry of rectangular block triangular matrices

Let D be any division ring, and let T（mi,ni,k） be the set of k × k （k ≥ 2） rectangular block triangular matrices over D. For A, B ∈ T（mi,ni,k）, if rank（A - B） = 1, then A and B are said to be adjacent and denoted by A -B. A map T ： T（mi,ni,k） -〉 T（mi,ni,k） is said to be an adjacency preserving map in both directions if A - B if and only if φ（A） φ（B）. Let G be the transformation group of all adjacency preserving bijections in both directions on T（mi,ni,k）. When m1,nk ≥ 2, we characterize the algebraic structure of G, and obtain the fundamental theorem of rectangular block triangular matrices over D.     

Commuting graphs of groups and related numerical parameters

Given a finite group G, we denote by Δ(G) the commuting graph of G which is defined as follows: the vertex set is G and two distinct vertices x and y are joined by an edge if and only if xy = yx. Clearly, Δ(G) is always connected for any group G. We denote by κ(G) the number of spanning trees of Δ(G). In the present paper, among other results, we first obtain the value κ(G) for some specific groups G, such as Frobenius groups, Dihedral groups, AC-groups, etc. Next, we characterize the alternating group A₅, in the class of nonsolvable groups through its tree-number κ(A₅). Finally, we classify the finite groups for which the power graph and the commuting graph coincide.