Mathieu groups and its degree prime-power graphs

Let cd(G) be the set of irreducible complex character degrees of a finite group G. The degree graph of G related to cd(G) was defined. It was proved many finite simple groups (but not all Mathieu groups) are uniquely determined by their orders and degree graphs. We hope to define a new graph related to cd(G) such that more simple groups can be uniquely determined by their orders and this newly defined graphs. Here a degree prime-power graph is defined and it is proved that all Mathieu groups can be determined uniquely by their orders and degree prime-power graphs.     

生成树与图的结构

在网络研究中,人们需要将图分解为指定的结构,来研究网络的普适性、鲁棒又脆弱性,探索网络进化、动力学复杂性、节点多样性、时空演化复杂性等.生成树与图的结构得到研究,海林图,唯一圈图,具有特殊完美匹配树等图的结构得到刻画.     

赋权图中的路和圈

本文研究了赋权图中的最长路和最长圈,将关于非赋权图中最长路和最长圈的一些结果推广到赋权图上.     

Small vertex‐transitive and Cayley graphs of girth six and given degree: an algebraic approach

We examine the existing constructions of the smallest known vertex‐transitive graphs of a given degree and girth 6. It turns out that most of these graphs can be described in terms of regular lifts of suitable quotient graphs. A further outcome of our analysis is a precise identification of which of these graphs are Cayley. We also investigate higher level of transitivity of the smallest known vertex‐transitive graphs of a given degree and girth 6 and relate their constructions to near‐difference sets. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:265‐284, 2011     

$R(G)\ge -1$的图族伴随多项式最小根极值的刻画

本文引入了图族伴随多项式的最小根极值,用它刻画了特征标不小于$-1$的图族伴随多项式的最小根极值,给出了其对应的极图, 并由此得到了一些有关这些图族伴随多项式最小根序关系的新结果.     

关于几类图族伴随多项式的第四项系数

主要研究了几类图族伴随多项式第四项系数的规律，此结果有助于进一步讨论这些图族补图的色唯一性、色等价划分．     

具有最小度距离的双圈图

记G（n）为所有n阶连通简单双圈图所构成的集合．本文主要讨论G（n）按其度距离从小到大进行排序的问题，并确定了该序的前两个图及其相应的度距离，其中具有最小度距离的图是由星图K1,n-1的一个悬挂点与另外两个悬挂点之间各连上一条边所得的图Sn．     

Forcing highly connected subgraphs

A theorem of Mader states that highly connected subgraphs can be forced in finite graphs by assuming a high minimum degree. We extend this result to infinite graphs. Here, it is necessary to require not only high degree for the vertices but also high vertex‐degree (or multiplicity) for the ends of the graph, that is, a large number of disjoint rays in each end. We give a lower bound on the degree of vertices and the vertex‐degree of the ends which is quadratic in k, the connectedness of the desired subgraph. In fact, this is not far from best possible: we exhibit a family of graphs with a degree of order 2^k at the vertices and a vertex‐degree of order k log k at the ends which have no k‐connected subgraphs. Furthermore, if in addition to the high degrees at the vertices, we only require high edge‐degree for the ends (which is defined as the maximum number of edge‐disjoint rays in an end), Mader's theorem does not extend to infinite graphs, not even to locally finite ones. We give a counterexample in this respect. But, assuming a lower bound of at least 2k for the edge‐degree at the ends and the degree at the vertices does suffice to ensure the existence (k + 1)‐edge‐connected subgraphs in arbitrary graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 331–349, 2007     

具有最大度距离的单圈图

设U (n)是具有n个顶点的所有单圈图的集合,G(3; n- 3)是由一个三角形C3粘上一条悬挂路P_(n-3)得到的单圈图.本文将证明当n 5时具有最大度距离的单圈图是G(3; n - 3).     

Colouring triangle-free intersection graphs of boxes on the plane

We prove that intersection graphs of boxes on the plane with girth 6 and 8 are 3- and 2-degenerate, respectively. This implies that these graphs are 4- and 3-list-colourable, respectively.     

Rainbow matchings in Dirac bipartite graphs

We show the existence of rainbow perfect matchings in μn‐bounded edge colorings of Dirac bipartite graphs, for a sufficiently small μ > 0. As an application of our results, we obtain several results on the existence of rainbow k‐factors in Dirac graphs and rainbow spanning subgraphs of bounded maximum degree on graphs with large minimum degree.     

On the minimum degree,edge-connectivity and connectivity of power graphs of finite groups

In this paper, the minimum degree of power graphs of certain cyclic groups, abelian p-groups, dihedral groups and dicyclic groups are obtained. It is ascertained that the edge-connectivity and minimum degree of power graphs are equal, and consequently, the minimum disconnecting sets of power graphs of the aforementioned groups are determined. In order to investigate the equality of connectivity and minimum degree of power graphs, certain necessary conditions for finite groups and a necessary and su?cient condition for finite cyclic groups are obtained. Moreover, the equality is discussed for the power graphs of abelian p-groups, dihedral groups and dicyclic groups.     

A family of graphs and the degree/diameter problem

We investigate a family of graphs relevant to the problem of finding large regular graphs with specified degree and diameter. Our family contains the largest known graphs for degree/diameter pairs (3, 7), (3, 8), (4, 4), (5, 3), (5, 5), (6, 3), (6, 4), (7, 3), (14, 3), and (16, 2). We also find a new bound for (3, 6) by an unrelated method. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 118–124, 2001     

门槛图与度极大图

证明了门槛图与度极大图是一类图的两种不同说法,同时用图的对角限制极左矩阵刻画这一类图的结构。     

On the average degree of some irreducible characters of a finite group

Let G be a finite group and N be a non-trivial normal subgroup of G, such that the average degree of irreducible characters in $\mathrm{Irr}(G|N)$ is less than or equal to 16/5. Then, we prove that N is solvable. Also, we prove the solvability of G, by assuming that the average degree of irreducible characters in $\mathrm{Irr}(G|N)$ is strictly less than 16/5. We show that the bounds are sharp.     

Quasi‐random graphs with given degree sequences

It is now known that many properties of the objects in certain combinatorial structures are equivalent, in the sense that any object possessing any of the properties must of necessity possess them all. These properties, termed quasirandom, have been described for a variety of structures such as graphs, hypergraphs, tournaments, Boolean functions, and subsets of Z _n, and most recently, sparse graphs. In this article, we extend these ideas to the more complex case of graphs which have a given degree sequence. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

On lower bounds for the chromatic number in terms of vertex degree

In this paper we discuss the existence of lower bounds for the chromatic number of graphs in terms of the average degree or the coloring number of graphs. We obtain a lower bound for the chromatic number of K_1,t-free graphs in terms of the maximum degree and show that the bound is tight. For any tree T, we obtain a lower bound for the chromatic number of any K_2,t-free and T-free graph in terms of its average degree. This answers affirmatively a modified version of Problem 4.3 in [T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley, New York, 1995]. More generally, we discuss δ-bounded families of graphs and then we obtain a necessary and sufficient condition for a family of graphs to be a δ-bounded family in terms of its induced bipartite Turán number. Our last bound is in terms of forbidden induced even cycles in graphs; it extends a result in [S.E. Markossian, G.S. Gasparian, B.A. Reed, β-perfect graphs, J. Combin. Theory Ser. B 67 (1996) 1–11].     

Neighborhood degree lists of graphs

The neighborhood degree list (NDL) is a graph invariant that refines information given by the degree sequence and joint degree matrix of a graph and is useful in distinguishing graphs having the same degree sequence. We show that the space of realizations of an NDL is connected via a switching operation. We then determine the NDLs that have a unique realization by a labeled graph; the characterization ties these NDLs and their realizations to the threshold graphs and difference graphs.     

Minimal claw-free graphs

A graph G is a minimal claw-free graph (m.c.f. graph) if it contains no K _1,3 (claw) as an induced subgraph and if, for each edge e of G, G ™ e contains an induced claw. We investigate properties of m.c.f. graphs, establish sharp bounds on their orders and the degrees of their vertices, and characterize graphs which have m.c.f. line graphs. Support by the South African National Research Foundation is gratefully acknowledged.     

On circle graphs with girth at least five

Circle graphs with girth at least five are known to be 2-degenerate [A.A. Ageev, Every circle graph with girth at least 5 is 3-colourable, Discrete Math. 195 (1999) 229-233]. In this paper, we prove that circle graphs with girth at least g≥5 and minimum degree at least two contain a chain of g−4 vertices of degree two, which implies Ageev’s result in the case g=5. We then use this structural property to give an upper bound on the circular chromatic number of circle graphs with girth at least g≥5 as well as a precise estimate of their maximum average degree.