探索金鱼图的奇优美性

给出了奇优美图和二分奇优美图的概念,并定义了金鱼图,证明了在鱼头为不同图形的情况下,金鱼图仍然是奇优美的,且是二分奇优美的.还证明了:对一个奇优美图H和一棵二分奇优美树T,用一条边连接T的一个顶点和H的标号基点u_0后所得到的金鱼图仍是奇优美图.     

奇阶完备残差图

本文讨论奇阶完备残差图,证明了对于任意奇数n,不存在奇阶Kn-残差图.对任意奇数t≥3和n=2t,2t -2,2t-4构造了一类具有奇阶2n+t的Kn-残差图.我们证明了当n≡0(mod4)时,Kn-残差图的最小奇阶为5n/2+1;当n≡2(mod4)时,Kn-残差图的最小奇阶为5n/2,并且证明了相应的最小奇阶Kn-残差图的唯一性.     

有限素数度弧正则图

如果一个图的全自同构群在其弧集上正则,则称此图为弧正则图.本文刻画素数度的立方自由阶弧正则图,证明任何素数度2倍奇立方自由阶弧正则图都是正规或二部正规Cayley图,且不存在任意素数度4倍奇立方自由阶的弧正则图,推广了一些已知的结果,得到阶为8倍奇平方自由阶素数度弧正则图的分类,并发现新的弧正则图类.此外,基于所得的结果,我们提出一个猜想和有待后续研究的一些问题.     

图(C)2n的奇优美及其奇强协调性

该文定义了图(C)2n,并研究了该图的奇优美和奇强协调性.利用构造法分别给出了图(C)2n在n=4k(k≥2)、n=4k+2时的奇优美算法,在n=4kk≥2)时,的奇强协调算法,进而证明了图(C)2n在n=2k(k≥3)时是奇优美图,在n=4k(k≥2)时是奇强协调图等结论,从而推动了对图的奇优美性和奇强协调性的研究.最后提出猜想:当n=4k+2时,图(C)2n不是奇强协调图.     

最大匹配数为|V(G)|+4的Eta图的结构

一个奇圈上加两条奇长的悬挂路组成的图形,称为Eta图.从Eta图的构造出发,研究了最大匹配数为|V(G)|+4的Eta图,得到了10种满足条件的结构.     

伪完全二分图PK_(n,n)奇优美标号的计算机实现

给出了伪完全二分图PK_(n,n)的定义及性质,提出了该类图的奇优美标号算法,证明了算法的正确性及时间复杂度,从而证明了伪完全二分图的奇优美性.并给出了伪完全二分图PK_(n,n),当n=3,4,5的一种标号方法.     

关于图的余树的奇连通分支数的内插定理

本文研究了连通图的余树的奇连通分支数与其可定向嵌入的关系.我们先给出了关于连通图的余树的奇连通分支数的内插定理.作为其应用,我们推广了Xuong和刘彦佩关于图的最大亏格的计算公式,并且证明了如下结果:任意一个连通图G一定满足下列条件之一: (a)对于任意的满足γ(G)≤g≤γM(G)整数g,只要图G嵌入到可定向曲面Sg上,就存在支撑树T,使g-1/2β(G)-ω(T)),其中,γ(G)与γM(G)分别是图G的最小和最大亏格,β(G)与ω(T)分别是图G的Betti数和由T确定的余树的奇连通分支数; (b)对连通图G的任意一个支撑树T,G可以嵌入某个可定向曲面上使其恰好有ω(T) 1个面.特别地,我们给出了所有非平面的3-正则的Hamilton图G所嵌入的可定向曲面的亏格的计算公式.     

灯笼图的可定向嵌入亏格分布

本文主要利用联树法研究了图的亏格多项式,得到了一类新图(灯笼图)的嵌入亏格分布.证明了灯笼图和偶梯图的亏格分布具有相同的递推关系,从而得到了灯笼图的嵌入亏格分布的精确解.     

广义Petersen图的弱点传递性

图X称为弱点传递图如果X的自同态幺半群EndX在顶点集V(X)上的作用是传递的 .本文给出了广义Petersen图是二分图的充要条件 ,刻划了奇围长小于 9的广义Petersen图的弱点传递性 ,作为推论给出了所有h ≤ 1 5的弱点传递的广义Pe tersen图P(h ,t) .     

林的Cordial性

给出林是Cordial图的充要条件是它不是4k＋2个奇度树的并．     

Equistable graphs, general partition graphs, triangle graphs, and graph products

In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al.     

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

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

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

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

Independent packings in structured graphs

Packing a maximum number of disjoint triangles into a given graph G is NP-hard, even for most classes of structured graphs. In contrast, we show that packing a maximum number of independent (that is, disjoint and nonadjacent) triangles is polynomial-time solvable for many classes of structured graphs, including weakly chordal graphs, asteroidal triple-free graphs, polygon-circle graphs, and interval-filament graphs. These classes contain other well-known classes such as chordal graphs, cocomparability graphs, circle graphs, circular-arc graphs, and outerplanar graphs. Our results apply more generally to independent packings by members of any family of connected graphs. Research of both authors is supported by the Natural Sciences and Engineering Research Council of Canada.     

Oriented bipartite graphs and the Goldbach graph

In this paper, we study oriented bipartite graphs. In particular, we introduce “bitransitive” graphs. Several characterizations of bitransitive bitournaments are obtained. We show that bitransitive bitounaments are equivalent to acyclic bitournaments. As applications, we characterize acyclic bitournaments with Hamiltonian paths, determine the number of non-isomorphic acyclic bitournaments of a given order, and solve the graph-isomorphism problem in linear time for acyclic bitournaments. Next, we prove the well-known Caccetta-Häggkvist Conjecture for oriented bipartite graphs in some cases for which it is unsolved, in general, for oriented graphs. We also introduce the concept of undirected as well as oriented “odd-even” graphs. We characterize bipartite graphs and acyclic oriented bipartite graphs in terms of them. In fact, we show that any bipartite graph (acyclic oriented bipartite graph) can be represented by some odd-even graph (oriented odd-even graph). We obtain some conditions for connectedness of odd-even graphs. This study of odd-even graphs and their connectedness is motivated by a special family of odd-even graphs which we call “Goldbach graphs”. We show that the famous Goldbach's conjecture is equivalent to the connectedness of Goldbach graphs. Several other number theoretic conjectures (e.g., the twin prime conjecture) are related to various parameters of Goldbach graphs, motivating us to study the nature of vertex-degrees and independent sets of these graphs. Finally, we observe Hamiltonian properties of some odd-even graphs related to Goldbach graphs for a small number of vertices.     

Cover-incomparability graphs and chordal graphs

The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs.     

Edge-primitive Cayley graphs on abelian groups and dihedral groups

A graph is called edge-primitive if its automorphism group acts primitively on its edge set. In 1973, Weiss (1973) determined all edge-primitive graphs of valency three, and recently Guo et al. (2013,2015) classified edge-primitive graphs of valencies four and five. In this paper, we determine all edge-primitive Cayley graphs on abelian groups and dihedral groups.     

Bounds on the clique-transversal number of regular graphs

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted Tc(G),is the minimum cardinality of a clique- transversal set in G.In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound.Also,we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound.     

Introducing subclasses of basic chordal graphs

Basic chordal graphs arose when comparing clique trees of chordal graphs and compatible trees of dually chordal graphs. They were defined as those chordal graphs whose clique trees are exactly the compatible trees of its clique graph.In this work, we consider some subclasses of basic chordal graphs, like hereditary basic chordal graphs, basic DV and basic RDV graphs, we characterize them and we find some other properties they have, mostly involving clique graphs.     

On magic and supermagic circulant graphs

A graph is called magic (supermagic) if it admits a labelling of the edges by pairwise different (and consecutive) integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In the paper, we characterize magic circulant graphs and 3-regular supermagic circulant graphs. We establish some conditions for supermagic circulant graphs.