A Note on Acyclic Edge Colouring of Star Graph Families

A proper edge colouring f of a graph G is called acyclic if there are no bichromatic cycles in the graph. The acyclic edge chromatic number or acyclic chromatic index, denoted by , is the minimum number of colours in an acyclic edge colouring of G. In this paper, we discuss the acyclic edge colouring of middle, central, total and line graphs of prime related star graph families. Also exact values of acyclic chromatic indices of such graphs are derived and some of their structural properties are discussed.

全着色临界图

本文定义了全着色临界图,并证明了对于 |{v|d(v)=△(G),v∈6V(G)}|≥3的全着色边临界图G(V.E),有 xт(G)=△(G)+2.其中△(G)表示G的最大度,xт(G)表示G的全色数.

基于图论方法的自动优化排课模型研究

排课问题是高校教务管理工作中劳动强度大且复杂费时的一项核心工作,目前还只能手工凭经验排课,在信息处理自动化不断普及的今天,显得极不协调,原因在于还没有一个行之有效的自动化排课模型。排课过程有很多不允许冲突的关联要素,一但冲突就会打乱正常的教学秩序导致教学事故,这是排课模型的研究难点。时间冲突是最基本的冲突限制,如:在同一个课时内,不能安排一个教师给两个班级上课,一个班级也不能同时应付两个老师的课。本文对笔者曾经提出的基于图论方法实现自动化排课、调课和优化的排课模型进行了扩展,不但从理论上彻底避免了各种冲突的可能性,并且可以大大提高排课的效率。

临界图的边数

本文研究了△－临界图的边数下界，其中△＝１０，１１，１２。

关于9-临界图边数的下界

本文给出了9-临界图边数的下界:m≥118/39 n,其中n为点数,m为边数。

完全图的强边着色

如果图G有一个合理边着色,且图G中所有顶点上的关联边着色集合都互不相同,则这种合理边着色又称为图G的强边着色。具有强边着色的图称为图G的强边着色图。使图G有强边着色的最小色数称为图G的强边色数。本文利用强边着色矩阵,讨论了完全图的强边着色及其分类,证明了:当n是奇数时,图Kn是一个第二类强边着色图,且χs′(Kn)=Δ(Kn)+1;当n是偶数时,图Kn是一个第三类强边着色图,且χs′(Kn)=Δ(Kn)+2。或者,χs′(Kn)=3+2[(n-2)/2],这里[x]表示取小于、等于x的最大整数。

完全图的准强边着色图的计数

使用准强边着色矩阵讨论了完全图的准强边着色图的计数。

完全图K_v的2因子分解与圈着色

阐明了完全图Kv的1因子分解和2因子分解的基本思路。分别证明了K2n的2因子分解定理和K2n+1的2因子分解定理。介绍了若干个完全图Kv的2因子分解的全过程。

准强边着色图的分类

如果图G已有一个合理边着色,使得图G中所有相邻顶点间的关联边着色集合相互不同,则这种边着色称为图G的准强边着色。具有准强边着色的图称为准强边着色图,并对准强边着色图给出一个分类。

低度 Halin 图的点边全色数

证明了对于Δ（Ｇ）＝４的任一Ｈａｌｉｎ图Ｇ，都有χｖｅ（Ｇ）＝５，此处Δ（Ｇ）和χｖｅ（Ｇ）分别表示图Ｇ的最大度数和点边全色数；对于Δ（Ｇ）＝３的Ｈａｌｉｎ图Ｇ的点边全色数作了初步的探讨。

关于边着色临界图的一个问题

H.P.Yap在[1]中提出这样一个问题,是否存在偶阶边着色8临界图,它除了有一个2度点和两个3度点外其余的都是8度点?作为本文定理推论的一个特殊情形给出了这个问题的否定性答案。

图P_n^k的着色

设k是一个正整数,在含有n个顶点的路Pn=v1v2…vn上,当且仅当两点的距离为k(k≥2)时增加一条边,这样所得到的图叫做Pnk(v1,vn),有时Pkn(v1,vn)也简记为Pnk.论文研究图Pnk的点着色、边着色和点、边全着色,得到图Pnk的点色数、边色数和图Pnk满足点、边全着色猜想等结论.

平面图为第一类图的一个充分条件

边色数为最大度的图是第一类图。如果G是一个最大度为6的平面图,且对于每一个顶点v,存在一个整数kv∈{3,4,5},使得v∈kv-C,那么G是第一类图,这里,符号v∈kv-C表示v不在一个kv-圈上。

完全图K_(2n+1)的n个H圈的分解方法

提出了完全图K2n+1分解成n个边不相交的H圈的两种方法.阐明了完全图K2n+1的2因子分解的基本思路.介绍了完全图K17的H圈分解的全过程.

基于完全二分图矩阵的△(G)-边着色求解完全图K_(4n)的完备匹配

给出了边矩阵和循环赛图的定义,提出了基于n(n-1)/2个完全二分图矩阵的△(G′)-边着色求解完全图K4n的完备匹配Mi的算法。阐明了循环赛图K(2i)n的构造的基本思路,介绍了完全图K20的△(G′)个完备匹配Mi的划分过程。

边临界图

本文定义了边临界图,并对其进行了研究,主要得到了以下性质:1)若G是△(G)边临界图,则G必为星图S△(G);2)若G是△(G)+1边临界图,则G没有割边;3)若G是△(G)+1边临界图,则对任意边uv,有d(u)+d(v)≥△(G)+2;4)若G是△(G)=3的简单连通图,且ν(G)是偶数,χ/(G)=△(G)+1,则存在点v∈V(G),使χ/(G-v)=χ/(G)=△(G)+1。此外,我们还提出猜想:"若G是简单图,G是△(G)+1边临界图,则ν(G)为奇数",并证明了此猜想与猜想"若G是简单图,ν(G)是偶数,χ/(G)=△(G)+1,则存在点v∈V(G),使χ/(G-v)=△(G)+1。"是等价的等结论。

基于图论的排课问题

课表的编排过程可以理解为是具体在哪个时间、哪个地点上某一门课程的问题。根据排课过程中必须满足的一些约束条件,利用图论可以解决教师和上课班级在时间和空间上的具体安排。

广义图K(5,n)的边色数

本文给出了完全图Ｋ５的广义图Ｋ（５，ｎ）的一种正常边着色法，从而解决了这类图的边色数．

全着色边临界图的一个注记

研究了全着色边临界图的结构,证明了对于△≥5的全着色边临界图G(V,E),若u∈V(G),d(u)=3,uvi∈E(G)(i=1,2,3),则△-1≤d(vi)≤△.

关于图的3—边色数

本文定义了图的r—边色数,研究了一般图的3—边色数的界和一些特殊图类的3—边色数,给出了图与其补图的3—边色数之间的关系。