Even signings,signed switching classes,and (−1, 1)-matrices

In this paper, algebraic and combinatorial techniques are used to establish results concerning even signings of graphs, switching classes of signed graphs, and (?1, 1)-matrices. These results primarily deal with enumeration of isomorphism types, and determining whether there are fixed elements under the action of automorphisms. A formula is given for the number of isomorphism types of even signings of any fixed simple graph. This is shown to be equal to the number of isomorphism types of switching classes of signings of the graph. A necessary and sufficient criterion is found for all switching classes fixed by a given graph automorphism to contain signings fixed by that automorphism. It is determined whether this criterion is met for all automorphisms of various graphs, including complete graphs, which yields a known result of Mallows and Sloane. As an application, a formula is developed for the number of H-equivalence classes of (?1, 1)-matrices of fixed size. Independently, using Molien's theorem and following a suggestion of Cameron's, generating series for these numbers are given. As a final application, a necessary and sufficient condition that a square (?1, 1)-matrix be switching equivalent to a symmetric matrix is given.     

Six-flows on almost balanced signed graphs

In 1983, Bouchet conjectured that every flow-admissible signed graph admits a nowhere-zero 6-flow. By Seymour's 6-flow theorem, Bouchet's conjecture holds for signed graphs with all edges positive. Recently, Rollová et al proved that every flow-admissible signed cubic graph with two negative edges admits a nowhere-zero 7-flow, and admits a nowhere-zero 6-flow if its underlying graph either contains a bridge, or is 3-edge-colorable, or is critical. In this paper, we improve and extend these results, and confirm Bouchet's conjecture for signed graphs with frustration number at most two, where the frustration number of a signed graph is the smallest number of vertices whose deletion leaves a balanced signed graph.     

开关图的几个代数性质

首先对开关图的自同构群进行了研究,随即讨论了它的点传递性,并得到Calyley图的开关图依然是Cayley图.     

Automorphisms of Maps with a Given Underlying Graph and Their Application to Enumeration

A graph is called a semi-regular graph if its automorphism group action on its ordered pair of adjacent vertices is semi-regular. In this paper, a necessary and sufficient condition for an automorphism of the graph F to be an automorphism of a map with the underlying graph F is obtained. Using this result, all orientation-preserving automorphisms of maps on surfaces (orientable and non-orientable) or just orientable surfaces with a given underlying semi-regular graph F are determined. Formulas for the numbers of non-equivalent embeddings of this kind of graphs on surfaces (orientable, non-orientable or both) are established, and especially, the non-equivalent embeddings of circulant graphs of a prime order on orientable, non-orientable and general surfaces are enumerated.     

图的好符号星控制数

引入了图的好符号星控制的概念,求出了欧拉图、完全二部图、完全图和轮图的好符号星控制数,并改进了图的符号星控制数的两个上界.     

Main eigenvalues and automorphisms of a graph

We study some aspects of the relationship between algebras associated with graphs and automorphism groups. We study an algebra generated by the adjacent matrix of a graph and the all ones matrix, and derive a lower bound for the rank of the automorphism group of a graph. If a graph attains the equality in the above bound, it is calledextremal. We also describe some properties and examples of extremal graphs.     

Main eigenvalues and automorphisms of a graph

We study some aspects of the relationship between algebras associated with graphs and automorphism groups. We study an algebra generated by the adjacent matrix of a graph and the all ones matrix, and derive a lower bound for the rank of the automorphism group of a graph. If a graph attains the equality in the above bound, it is calledextremal. We also describe some properties and examples of extremal graphs.     

Symmetry in complex networks

We consider the size and structure of the automorphism groups of a variety of empirical ‘real-world’ networks and find that, in contrast to classical random graph models, many real-world networks are richly symmetric. We construct a practical network automorphism group decomposition, relate automorphism group structure to network topology and discuss generic forms of symmetry and their origin in real-world networks. We also comment on how symmetry can affect network redundancy and robustness.     

Enumeration of weak isomorphism classes of signed graphs

A signed graph is a graph in which each line has a plus or minus sign. Two signed graphs are said to be weakly isomorphic if their underlying graphs are isomorphic through a mapping under which signs of cycles are preserved, the sign of a cycle being the product of the signs of its lines. Some enumeration problems implied by such a definition, including the problem of self-dual configurations, are solved here for complete signed graphs by methods of linear algebra over the two-element field. It is also shown that weak isomorphism classes of complete signed graphs are equal in number to other configurations: unlabeled even graphs, two-graphs and switching classes.     

Geometric automorphism groups of graphs

Constructing symmetric drawings of graphs is NP-hard. In this paper, we present a new method for drawing graphs symmetrically based on group theory. More formally, we define an n-geometric automorphism group as a subgroup of the automorphism group of a graph that can be displayed as symmetries of a drawing of the graph in n dimensions. Then we present an algorithm to find all 2- and 3-geometric automorphism groups of a given graph. We implement the algorithm using Magma [〈http://magma.maths.usyd.edu.au〉] and the experimental results show that our approach is very efficient in practice. We also present a drawing algorithm to display 2- and 3-geometric automorphism groups.     

Isomorphisms of adjoint Chevalley groups over integral domains

It is shown that every automorphism of an adjoint Chevalley group over an integral domain containing the rational number field is uniquely expressible as the product of a ring automorphism, a graph automorphism and an inner automorphism while every isomorphism between simple adjoint Chevalley groups can be expressed uniquely as the product of a ring isomorphism, a graph isomorphism and an inner automorphism. The isomorphisms between the elementary subgroups are also found having analogous expressions.

     

Destroying automorphisms by fixing nodes

The fixing number of a graph G is the minimum cardinality of a set S⊂V(G) such that every nonidentity automorphism of G moves at least one member of S, i.e., the automorphism group of the graph obtained from G by fixing every node in S is trivial. We provide a formula for the fixing number of a disconnected graph in terms of the fixing numbers of its components and make some observations about graphs with small fixing numbers. We determine the fixing number of a tree and find a necessary and sufficient condition for a tree to have fixing number 1.     

Signed graphs

A signed graph is a graph with a sign attached to each arc. This article introduces the matroids of signed graphs, which generalize both the polygon matroids and the even-circle (or unoriented cycle) matroids of ordinary graphs. The concepts of balance, switching, restriction and contraction, double covering graphs, and linear representation of signed graphs are treated in terms of the matroid, and a matrix-tree theorem for signed graphs is proved. The examples treated include the all-positive and all-negative graphs (whose matroids are the polygon and even-circle matroids), sign-symmetric graphs (related to the classical root systems), and signed complete graphs (equivalent to two-graphs).Replacing the sign group by an arbitrary group leads to voltage graphs. Most of our results on signed graphs extend to all voltage graphs.     

Factor group of the automorphism group of a matroid basis graph with respect to the automorphism group of the matroid

Any automorphism of a matroid induces an automorphism of its basis graph. We try to determine what can be said concerning the automorphisms of the basis graph which are not induced by matroids' automorphisms. In particular, we determine the structure of the factor group of the automorphism group of the basis graph with respect to the automorphism group of the matroid, in the event that this factor group exists.     

二面体群D_(2n)的4度正规Cayley图

设G是有限群,S是G的不包含单位元1的非空子集．定义群G关于S的 Cayley(有向)图X=Cay(G,S)如下:V(x)=G,E(X)={(g,sg)|g∈G,s∈S}． Cayley图X=Cay(G,S)称为正规的如果R(G)在它的全自同构群中正规．图X称为1-正则的如果它的全自同构群在它的弧集上正则作用．本文对二面体群D2n以Z22 为点稳定子的4度正规Cayley图进行了分类．     

Torsion units for some almost simple groups

We investigate the Zassenhaus conjecture regarding rational conjugacy of torsion units in integral group rings for certain automorphism groups of simple groups. Recently, many new restrictions on partial augmentations for torsion units of integral group rings have improved the effectiveness of the Luther-Passi method for verifying the Zassenhaus conjecture for certain groups. We prove that the Zassenhaus conjecture is true for the automorphism group of the simple group PSL(2, 11). Additionally we prove that the Prime graph question is true for the automorphism group of the simple group PSL(2, 13).     

Symmetries of the Partial Order of Traces

This paper deals with the automorphism group of the partial order of finite traces. We show that any group can arise as such an automorphism group if we allow arbitrary large dependence alphabets. Restricting to finite dependence alphabets, the automorphism groups are profinite and possess only finitely many simple decomposition factors. Finally, we show that the partial order associated with the Rado graph as dependence alphabet does not give rise to a homogeneous domain thereby answering an open question from Boldi, P., Cardone, F. and Sabadini, N. (1993).     

Graph theoretic approach to parallel gene assembly

We study parallel complexity of signed graphs motivated by the highly complex genetic recombination processes in ciliates. The molecular gene assembly operations have been modeled by operations of signed graphs, i.e., graphs where the vertices have a sign + or −. In the optimization problem for signed graphs one wishes to find the parallel complexity by which the graphs can be reduced to the empty graph. We relate parallel complexity to matchings in graphs for some natural graph classes, especially bipartite graphs. It is shown, for instance, that a bipartite graph G has parallel complexity one if and only if G has a unique perfect matching. We also formulate some open problems of this research topic.     

Classifying cubic symmetric graphs of order 10p or 10p~2

A graph is called s-regular if its automorphism group acts regularly on the set of its s-arcs. In this paper, the s-regular cyclic or elementary abelian coverings of the Petersen graph for each s ≥ 1 are classified when the fibre-preserving automorphism groups act arc-transitively. As an application of these results, all s-regular cubic graphs of order 10p or 10p2 are also classified for each s ≥ 1 and each prime p, of which the proof depends on the classification of finite simple groups.     

图的符号边控制数

图的符号边控制数有着许多重要的应用背景.已知它的计算是NP-完全问题,因而确定其精确值有重要意义.本文确定了图F*n+1、H n和P*n的符号边控制数.