The Semi-Arc Automorphism Group of a Graph with Application to Map Enumeration

A map is a connected topological graph cellularly embedded in a surface. For a given graph Γ, its genus distribution of rooted maps and embeddings on orientable and non-orientable surfaces are separately investigated by many researchers. By introducing the concept of a semi-arc automorphism group of a graph and classifying all its embeddings under the action of its semi-arc automorphism group, we find the relations between its genus distribution of rooted maps and genus distribution of embeddings on orientable and non-orientable surfaces, and give some new formulas for the number of rooted maps on a given orientable surface with underlying graph a bouquet of cycles B_n, a closed-end ladder L_n or a Ringel ladder R_n. A general scheme for enumerating unrooted maps on surfaces(orientable or non-orientable) with a given underlying graph is established. Using this scheme, we obtained the closed formulas for the numbers of non-isomorphic maps on orientable or non-orientable surfaces with an underlying bouquet B_n in this paper.     

A Generalization of Noncommuting Graph via Automorphisms of a Group

Let G be a group. By using a family 𝒜 of subsets of automorphisms of G, we introduced a simple graph Γ_𝒜(G), which is a generalization of the non-commuting graph. In this paper, we study the combinatorial properties of Γ_𝒜(G).     

图的可定向嵌入的标根可数性

给定一族图G,可定向曲面上存在多少个以其中某个图为基础图的标根地图？采用图的自同构群对图在可定向曲面上的嵌入集合进行分类，该文解决了这个问题，同时得到了求解计数函数f^r(M)的一种新的方法。     

Circulant Double Coverings of a Circulant Graph of Valency Four

Several isomorphism classes of graph coverings of a graph G have been enumerated by many authors (see [3], [8]–[15]). A covering of G is called circulant if its covering graph is circulant. Recently, the authors [4] enumerated the isomorphism classes of circulant double coverings of a certain kind, called typical, and showed that no double covering of a circulant graph of valency 3 is circulant. In this paper, the isomorphism classes of connected circulant double coverings of a circulant graph of valency 4 are enumerated. As a consequence, it is shown that no double covering of a non-circulant graph G of valency 4 can be circulant if G is vertex-transitive or G has a prime power of vertices. The first author is supported by NSF of China (No. 60473019) and by NKBRPC (2004CB318000), and the second author is supported by Com²MaC-KOSEF (R11-1999-054) in Korea.     

Normality of Tetravalent Cayley Graphs of Odd Prime-cube Order and Its Application

Let p be an odd prime. In this paper we prove that all tetravalent connected Cayley graphs of order p^3 are normal. As an application, a classification of tetravalent symmetric graphs of odd prime-cube order is given.     

二秩无扭群的自同构群和只有两个自同构的二秩无扭群

本文利用Ｋｕｒǒｓ不变量理论和不定方程理论，讨论了二秩无扭群的自同构群，以及有零高元的二秩无扭群只有两个自同构的充要条件．     

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

The Multiplicative Automorphisms of a Finite Nearfield,with an Application

In this article, we look at the automorphisms of the multiplicative group of finite nearfields. We find partial results for the actual automorphism groups and use counting techniques for the size of all finite nearfields. We then show that these results can be used in order to count the number of near vector spaces of a given dimension over a given nearfield, up to isomorphism.     

[a,b]-因子包含给定圈的充分条件

设G是一个图且a,b是非负整数,a≤b.图G的一个[a,b]-因子是图G的一个支撑子图H且满足对所有的x∈V(G),a≤dH(x)≤b都成立.给出了图中[a,b]-因子包含给定圈的一个充分条件.     

K_(1,n)-free图具有给定性质的[a,b]-因子的一个充分条件

图G称为K1,n-free图,如果它不含K1,n作为其导出子图.对K1,n-free图具有给定性质的[a,b]-因子涉及到最小度条件进行了研究,得到一个充分条件.     

Duality Maps of Finite Abelian Groups and Their Applications to Spin Models

Duality maps of finite abelian groups are classified. As a corollary, spin models on finite abelian groups which arise from the solutions of the modular invariance equations are determined as tensor products of indecomposable spin models. We also classify finite abelian groups whose Bose-Mesner algebra can be generated by a spin model.     

On Connection Between the Structure of a Finite Group and the Properties of Its Prime Graph

It is shown that the condition of nonadjacency of 2 and at least one odd prime in the Gruenberg-Kegel graph of a finite group G under some natural additional conditions suffices to describe the structure of G; in particular, to prove that G has a unique nonabelian composition factor. Applications of this result to the problem of recognition of finite groups by spectrum are also considered.Original Russian Text Copyright © 2005 Vasilev A. V.The author was supported by the Russian Foundation for Basic Research (Grant 05-01-00797), the State Maintenance Program for the Leading Scientific Schools of the Russian Federation (Grant NSh-2069.2003.1), the Program Development of the Scientific Potential of Higher School of the Ministry for Education of the Russian Federation (Grant 8294), the Program Universities of Russia (Grant UR.04.01.202), and a grant of the Presidium of the Siberian Branch of the Russian Academy of Sciences (No. 86-197).__________Translated from Sibirskii Matematicheskii Zhurnal, Vol. 46, No. 3, pp. 511–522, May–June, 2005.     

The Annihilating-Ideal Graph of a Commutative Ring with Respect to an Ideal

For a commutative ring R with identity, the annihilating-ideal graph of R, denoted 𝔸𝔾(R), is the graph whose vertices are the nonzero annihilating ideals of R with two distinct vertices joined by an edge when the product of the vertices is the zero ideal. We will generalize this notion for an ideal I of R by replacing nonzero ideals whose product is zero with ideals that are not contained in I and their product lies in I and call it the annihilating-ideal graph of R with respect to I, denoted 𝔸𝔾 _I (R). We discuss when 𝔸𝔾 _I (R) is bipartite. We also give some results on the subgraphs and the parameters of 𝔸𝔾 _I (R).     

Graph Sharing Game and the Structure of Weighted Graphs with a Forbidden Subdivision

In the graph sharing game, two players share a connected graph G with nonnegative weights assigned to the vertices claiming and collecting the vertices of G one by one, while keeping the set of all claimed vertices connected through the whole game. Each player wants to maximize the total weight of the vertices they have gathered by the end of the game, when the whole G has been claimed. It is proved that for any class of graphs with an odd number of vertices and with forbidden subdivision of a fixed graph (e.g., for the class of planar graphs with an odd number of vertices), there is a constant such that the first player can secure at least the proportion of the total weight of G whenever . Known examples show that such a constant does no longer exist if any of the two conditions on the class (an odd number of vertices or a forbidden subdivision) is removed. The main ingredient in the proof is a new structural result on weighted graphs with a forbidden subdivision.     

An Extension of Set-Valued Contraction Principle for Mappings on a Metric Space with a Graph and Application

In this paper, we obtain an existence theorem for fixed points of contractive set-valued mappings on a metric space endowed with a graph. This theorem unifies and extends several fixed point theorems for mappings on metric spaces and for mappings on metric spaces endowed with a graph. As an application, we obtain a theorem on the convergence of successive approximations for some linear operators on an arbitrary Banach space. This result yields the well-known Kelisky–Rivlin theorem on iterates of the Bernstein operators on C[0,1].     

一类边裂图边优美的充要条件

指出了一类边裂图SEP(K1,n,f)与图K1,n的边优美性的差异.得到了对任意自然数m>0,SPE(K1,4m+1,f)不是边优美的,以及SEP(K1,n,f)是边优美图的充要条件.     

Almost-Normed Spaces of Functions with Given Asymptotics, Lagrangian Asymptotics, and Their Application to Ordinary Differential Equations

The concept of almost-normed spaces is introduced. It is proved that the space of sufficiently smooth functions asymptotically approximating to polynomials (of degrees no higher than a given one) as their argument tends to infinity is an almost-normed space. It is demonstrated that this space is a complete metric space with respect to the metrics generated by the almost-norm introduced. The space of functions strongly asymptotically approximating to polynomials is defined, and its embedding into the space of functions asymptotically approximating to polynomials is proved. The results obtained give a new approach to studying boundary-value problems with asymptotic initial value data at singular points of ordinary differential equations.     

Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree

For a loopless multigraph G, the fractional arboricity Arb(G) is the maximum of over all subgraphs H with at least two vertices. Generalizing the Nash‐Williams Arboricity Theorem, the Nine Dragon Tree Conjecture asserts that if , then G decomposes into forests with one having maximum degree at most d. The conjecture was previously proved for ; we prove it for and when and . For , we can further restrict one forest to have at most two edges in each component. For general , we prove weaker conclusions. If , then implies that G decomposes into k forests plus a multigraph (not necessarily a forest) with maximum degree at most d. If , then implies that G decomposes into forests, one having maximum degree at most d. Our results generalize earlier results about decomposition of sparse planar graphs.