Precoloring extension for 2-connected graphs with maximum degree three

Let G=G(V,E) be a simple graph, L a list assignment with |L(v)|=Δ(G)∀v∈V and W⊆V an independent subset of the vertex set. Define to be the minimum distance between two vertices of W. In this paper it is shown that if G is 2-connected with Δ(G)=3 and G is not K₄ then every precoloring of W is extendable to a proper list coloring of G provided that d(W)≥6. An example shows that the bound is sharp. This result completes the investigation of precoloring extensions for graphs with |L(v)|=Δ(G) for all v∈V where the precolored set W is an independent set.     

Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs

A decomposition of a complete graph into disjoint copies of a complete bipartite graph is called a ‐design of order n. The existence problem of ‐designs has been completely solved for the graphs for , for , K_{2, 3} and K_{3, 3}. In this paper, I prove that for all , if there exists a ‐design of order N, then there exists a ‐design of order n for all (mod ) and . Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved.     

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

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

半二面体群的小度数Cayley图

群G的一个Cayley图X=Cay(G,S)称为正规的,如果右乘变换群R(G)在Aut X中正规.研究了4m阶半二面体群G=〈a,b a2m=b2=1,ab=am-1〉的3度和4度Cayley图的正规性,其中m=2r且r>2,并得到了几类非正规的Cayley图.     

强算术图

一个（p,q)-图G被为是强（k,d)-算术图,如果存在一个由G的顶点集到模q的整数群Zq的单射,使得相邻两顶点标号的和导出的边值为算术级数,k,k d,……,k (q-1)d,本文讨论了这类标号图的结构和一些性质。     

门槛图与度极大图

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

关于紧图和超紧图的几个结果

给出了一些 新的紧图,并对 不是超紧的紧图 作了一些讨论     

一类拟二面体群的四度Cayley图的正规性

群G的一个Cayley图X=Cay(G,S)称为正规的,如果右乘变换群R(G)在AutX中正规.研究了4m阶拟二面体群G=a,b|a~(2m)=b~2=1,a~b=a~(m+1)的4度Cayley图的正规性,其中m=2~r,且r2,并得到拟二面体群的Cayley图的同构类型.     

四圈图的Spread

图的spread定义为图的邻接矩阵的最大特征值与最小特征值的差.本文确定了n(n≥84)顶点四圈图中spread最大的唯一的图.     

Unitary Graphs

Unitary graphs are arc‐transitive graphs with vertices the flags of Hermitian unitals and edges defined by certain elements of the underlying finite fields. They played a significant role in a recent classification of a class of arc‐transitive graphs that admit an automorphism group acting imprimitively on the vertices. In this article, we prove that all unitary graphs are connected of diameter two and girth three. Based on this, we obtain, for any prime power , a lower bound of order on the maximum number of vertices in an arc‐transitive graph of degree and diameter two.     

正规Cayley图

综述了自１９９０年以来１２－传递图研究的一些新成果,正规Ｃａｙｌｅｙ图的相关结论。     

多重跳图的平面性

The infinite sequence {J^k5(G)} where Js(G) denotes the 5-jump graph of G, is planar if, and only if, G=cor(K3). For r-jump graph with r≥6, there does not exist a graph G such that the sequence {J^kr(G)} is planar.     

Cover-Incomparability Graphs of Posets

Cover-incomparability graphs (C-I graphs, for short) are introduced, whose edge-set is the union of edge-sets of the incomparability and the cover graph of a poset. Posets whose C-I graphs are chordal (resp. distance-hereditary, Ptolemaic) are characterized in terms of forbidden isometric subposets, and a general approach for studying C-I graphs is proposed. Several open problems are also stated.     

Taut Distance-Regular Graphs of Odd Diameter

Let denote a bipartite distance-regular graph with diameter D 4, valency k 3, and distinct eigenvalues ₀ > ₁ > ··· > _D. Let M denote the Bose-Mesner algebra of . For 0 i D, let E _i denote the primitive idempotent of M associated with _i . We refer to E ₀ and E _D as the trivial idempotents of M. Let E, F denote primitive idempotents of M. We say the pair E, F is taut whenever (i) E, F are nontrivial, and (ii) the entry-wise product E F is a linear combination of two distinct primitive idempotents of M. We show the pair E, F is taut if and only if there exist real scalars , such that _{i + 1 i + 1} – _{i – 1 i – 1} = _i ( _{i + 1} – _{i – 1}) + _i ( _{i + 1} – _{i – 1}) + (1 i D – 1)where ₀, ₁, ..., _D and ₀, ₁, ..., _D denote the cosine sequences of E, F, respectively. We define to be taut whenever has at least one taut pair of primitive idempotents but is not 2-homogeneous in the sense of Nomura and Curtin. Assume is taut and D is odd, and assume the pair E, F is taut. We show

三度边正则图的三个无限族

图X称为边正则图，若X的自同构群Aut(X)在X的边集上的作用是正则的．本文考察了三度边正则图与四度Cayley图的关系，给出了一个由四度Cayley图构造三度边正则图的方法，并且构造了边正则图的三个无限族．     

平衡子欧拉符号图及符号线图

符号图$S=(S^u,\sigma)$是以$S^u$作为底图并且满足$\sigma: E(S^u)\rightarrow\{+,-\}$. 设$E^-(S)$表示$S$的负边集. 如果$S^u$是欧拉的(或者分别是子欧拉的, 欧拉的且$|E^-(S)|$是偶数, 则$S$是欧拉符号图(或者分别是子欧拉符号图, 平衡欧拉符号图). 如果存在平衡欧拉符号图$S''$使得$S''$由$S$生成, 则$S$是平衡子欧拉符号图. 符号图$S$的线图$L(S)$也是一个符号图, 使得$L(S)$的点是$S$中的边, 其中$e_ie_j$是$L(S)$中的边当且仅当$e_i$和$e_j$在$S$中相邻,并且$e_ie_j$是$L(S)$中的负边当且仅当$e_i$和$e_j$在$S$中都是负边. 本文给出了两个符号图族$S$和$S''$,它们应用于刻画平衡子欧拉符号图和平衡子欧拉符号线图. 特别地, 本文证明了符号图$S$是平衡子欧拉的当且仅当$\not\in S$, $S$的符号线图是平衡子欧拉的当且仅当$S\not\in S''$.     

障碍拟阵图

Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.     

关于偶图的K—优美性

本文引进了图G(G_1,G_2,…,G_(|E(G)|))、G(G_1~(|E(G)|))的概念,此外,还引进了序优美图、可逆优美图、偶图的优美函数等概念,对于某些特殊的偶图,给出了利用小阶优美偶图构造大阶优美偶图的一种方法,由此证明了某些偶图是K-优美图。     

A Local Analysis of Imprimitive Symmetric Graphs

Let Г be a G-symmetric graph admitting a nontrivial G-invariant partition . Let Г be the quotient graph of Г with respect to . For each block B ∊ , the setwise stabiliser G_B of B in G induces natural actions on B and on the neighbourhood Г (B) of B in Г . Let G_(B) and G_[B] be respectively the kernels of these actions. In this paper we study certain “local actions" induced by G_(B) and G_[B], such as the action of G_[B] on B and the action of G_(B) on Г (B), and their influence on the structure of Г. Supported by a Discovery Project Grant (DP0558677) from the Australian Research Council and a Melbourne Early Career Researcher Grant from The University of Melbourne.     

Graphs equienergetic with edge-deleted subgraphs

The energy of a graph is the sum of the absolute values of the eigenvalues of its adjacency matrix. Two graphs are equienergetic if they have the same energy. We construct infinite families of graphs equienergetic with edge-deleted subgraphs.