图K(p,p)+S的色性

设G是简单图,G表示图G的补图,用P(G,λ)表示图G的色多项式。若P(G,λ)=P(H,λ),则称图G与H是色等价的,简单的表示H～G。记[G]={H|H～G}。若[G]={G},称G是色唯一的。设K(p,p)是一个二部图且S是完全图Kp的s条边组成的子集,K s(p,p)表示在K(p,p)的一个具有p个点的独立集中增加S中的所有边得到的图。本文中证明了当p≥s 2且S的边导出了子图是二部图时,[K s(p,p)]={Np V G|G∈[Kp-s]},其中Np V G表示Np和G的联图,Np=Kp,并给出了一个K s(p,p)色唯一的一个充要条件;进而部分的回答了Teo和Koh在Graph J Theory(1990)中提出的一个问题。     

图变换及其在图的最小无符号拉普拉斯特征值的应用北大核心CSCD

假定G是一个带有点集V(G)={v_(1),v_(2),···,v_(n)}的连通简单图,图G的邻接矩阵A(G)=(a_(ij))_(n×n),其中点vi与点vj相邻,则a_(ij)=1;否则a_(ij)=0。我们定义度矩阵D(G)=diag(dG(v_(1)),dG(v_(2)),···,dG(v_(n))),其中dG(v_(i))是图G中点v_(i)(1≤i≤n)的度数。定义图G的无符号拉普拉斯矩阵Q(G)=D(G)+A(G),因为Q(G)是一个半正定矩阵,所以可将其特征值设为λ_(1)(G)≥λ_(2)(G)≥···≥λ_(n)(G)≥0,其中特征值λn(G)也称为图G的最小无符号拉普拉斯特征值。对补图的最小无符号拉普拉斯特征值问题进行了研究,报告了相关问题的研究现状,给出了两种图变换,并且应用他们去确定所有双圈图的补图中最小无符号拉普拉斯特征值取最小的唯一图。     

交错群A_5的3度Cayley图

设G是一个有限群,S是群G的一个不含单位元1的子集,则G的关于S的Cayle图Γ=Cay(G,S)可由如下关系式定义:V(Γ)=GE(Γ)={(g,sg)|g∈G,s∈S}给出3度Cayley图Γ=Cay(As,S),即|S|=3时三个不同构类图的特征刻划,见定理1.     

特殊图b-色数的相关性质

图染色是图论中研究热点问题之一,在许多领域都有重要的应用.用χ(G)和φ(G)分别表示连通图G的色数和b-色数.对连通图R,S,称图G不含导出{R,S},如果图G不含同构于R和S的导出子图.本文证明了对任意连通的至少4个顶点的图R,S,连通(或者2-边连通或者2-连通)不含{R,S}的图G满足χ(G)=φ(G)当且仅当...     

图中具有分数(g,f)-因子的若干充分条件

设g和f分别是定义在图G的顶点集合V(G)上的整数值函数且对每个x∈V(G)有0≤g(x)≤f(x)。本文给出了一个图有分数(g,f)-因子的若干充分条件。     

图的森林图

本文中引进了连通图的森林图,它是树图的推广.研究了森林图的子图：邻接森林图和叶交换森林图.特别,邻接树图和线图是我们推广的特殊情况.进而,我们研究了这些图的性质并提出了可进一步研究的问题.     

关于图的分数k-可扩性的若干结果

一个图称为是分数k-可扩的,若图G含有k条边的对集且对图G的任意一个k条边的对集M,都存在G的一个分数1-因子Gh,使得对任意的e∈M有h(e)=1.我们研究了分数k-可扩图的特征,给出了带有某些约束的分数k-可扩图存在充分条件,以及极大分数k-可扩图的特征.     

图的2-距离控制数为[p/3]的必要条件

N.Sridharan等证明了阶数为p的2-距离控制数γ2(G)≤[p/3],并给出了p=3k(k=1,2,…)时,γ2(G)=p/3的充要条件.在这些结果的基础上,给出当p为任意正整数时,2γ(G)=[p/3]的一个必要条件:设G是阶数为p≥10的连通图,若2γ(G)=[p/3]且G A0,则G至少有一个悬挂点,这里A0是给定的图集.     

交错群A_5的4度连通对称图的分类

一个图Г称为G-对称的(symmetric).如果其同构群Aut(r)的一个子群G在图r的有向孤集(set of ordered pairs of adjacent vertices)上的作用是传递的(transitive).本文主要结果是:设图Г是4度对称图.全自同构群Aut(r)=A_5,则图r是且仅是如下图之一:(1)Г是15个点的完全图K_5的三维覆盖(3-fold cover)图.(2)Г是完全图K_5.     

路、圈的Mycielskian图的反魔术标号

令G=(V,E)是一个含有m条边的无向图.G的一个反魔术标号是指从边集E到集合{1,2,…,m}的一个双射,使得图上所有顶点的边权和都不相同.如果图G具有一个反魔术标号,则称G为反魔术图.Hartsfield和Ringel猜测:除K_2外所有连通图都是反魔术图.通过给出具体的反魔术边标号方案,证实了路、圈的Mycielskian图均为反魔术图.     

具有最小距离拉普拉斯谱半径的双圈图（英）

一个连通图的距离拉普拉斯矩阵的最大特征值称为这个图的距离拉普拉斯谱半径．本文中,我们先得到距离拉普拉斯谱半径的一个好的下界,然后利用这个下界确定了单圈图中具有最小距离拉普拉斯谱半径的唯一极图．最后,再次利用这个下界,并结合距离拉普拉斯矩阵的特征多项式确定出了双圈图中具有最小距离拉普拉斯谱半径的极图．     

条形图和圆环图数据占比映射的比较研究

目的 研究在观察时间受限制的条件下,条形图和圆环图在映射数据占总体比值关系时的优势。方法 实验设计了3种尺寸（占屏幕7.5%,15%,22%）和3种映射取值（1,1/2,1/3）的条形图和圆环图,被测对象对图形映射的数据占比进行判断,以获得2种形态的判断时间均值和错误率均值。实验使用计算机化实验生成系统E-prime收集数据,使用SPSS进行数据统计和分析。结果 映射取值为1、1/2、1/3条件下,条形图的3种尺寸判断时间均值均低于圆环图;条形图判断错误率均值为2.51%,低于圆环图的错误率4.03%;2种图的映射取值越小,判断的速度越慢。结论 条形图的映射判断速度和准确性比圆环图更具有优势,更适合应用于时空受限制的场景,有助于数据可视化设计时减少因数据堆集而导致的信息过载。     

弱罗马图和图的弱罗马控制的一些性质

罗马控制是一个有丰富历史背景和数学背景的典型控制问题,它与计算机科学、交通安全监管控制、企业安全生产监管控制、组合优化、监视系统和社会网络等领域密切相关,具有重要的理论意义和应用价值。图的弱罗马控制数是图的弱罗马控制函数的最小权,记为$\gamma_{r}(G)$。图 $G$ 的控制集的最小基数称为最小控制数,记为 $\gamma(G)$。若图 $G$ 满足 $\gamma_{r}(G)=2\gamma(G)$,则称图 $G$ 是弱罗马图。用构造法确定了路 $P_{3}$,星 $K_{1, t} (t\geq2)$,由星 $K_{1, t_{1}},K_{1, t_{2}},\cdots,K_{1, t_{n}}\,(t_{i}\geq3, i=1,2,\cdots,n)$ 的中心点依次连接成一条路所构成的树 $T$,或由它们的外点连接构成的树$T$ 是弱罗马图,并给出了弱罗马图和图的弱罗马控制的一些性质。     

路图与线图的一个综述

线图的概念最早是由Whitney提出的,在所有图的变换中,线图可能是研究最广泛的一种变换了。关于线图的研究已经有很多结果,路图变换是线图的一种自然推广。在这篇综述中,我们可以看到有时路图与线图的性质差异很大,有些问题对路图而言变得相当复杂和困难。这篇文章主要通过以下几个方面比较和总结了路图与线图的一些结果:基本事实,判定问题,刻画问题,贯穿性,连通度。     

Graph theoretic algorithm for automatic operation sequencing for progressive die design

The paper presents a formal graph representation scheme for stamping operation sequencing for sheetmetal progressive dies and a graph theoretic method for automatic determination of the stamping operation sequence. Operation relations are represented by two graphs: an operation precedence graph and an adjacency graph. The first represents precedence constraints defined by best manufacturing practices. The second represents geometric infeasibility relations between operations. Each operation is a member of both graphs. The graphs are automatically generated from a set of stamping operations, which in turn are associated with stamping features of a part. The operation precedence graph is then verified to be acyclic using a coloured Depth First Search. Based on the operation precedence graph, a modified topological sort algorithm is applied to cluster the operations into partially ordered sets. Finally, a graph-colouring algorithm is applied to the operation adjacency graph on the partially ordered operation sets. The algorithm is implemented in C++ and is fully integrated with SolidWorks computer-aided design system. A case study is presented to illustrate the algorithm.     

基于遗传算法的图关联着色算法

图的着色算法是一种典型的NP-完全问题。给出了一种用于图的关联着色的遗传算法。遗传算法用于进行全局搜索,从而有效的查找解空间。文中对关联色数为6的一个图进行了仿真实验,给出了该图的关联色数以及4种6-关联着色。用本文提出的算法,得到了完全图、完全多部图的关联色数。实验结果表明,本文设计的遗传算法可以很好的对关联着色猜想进行求解,获得问题的高质量的解。     

Topological Characterization of Book Graph and Stacked Book Graph

Degree based topological indices are being widely used in computer-aided modeling, structural activity relations, and drug designing to predict the underlying topological properties of networks and graphs. In this work, we compute the certain important degree based topological indices like Randic index, sum connectivity index, ABC index, ABC₄ index, GA index and GA₅ index of Book graph B_n and Stacked book graph B_m,n. The results are analyzed by using edge partition, and the general formulas are derived for the above-mentioned families of graphs.