广义de Bruijn和Kautz有向图的距离控制数

对于任意的正整数(?),强连通图G的顶点子集D被称为距离(?)-控制集,是指对于任意顶点v(?)D,D中至少含有一个顶点u,使得距离dG(u,v)≤(?)．图G距离(?)- 控制数γe(G)是指G中所有距离(?)-控制集的基数的最小者．本文给出了广义de Bruijn 和广义Kautz有向图的距离(?)-控制数的上界和下界,并且给出当它们的距离2-控制数达到下界时的一个充分条件．从而得到对于de Bruijn有向图B(d,k)的距离2-控制数γ2(B(d,k))= ．在该文结尾,我们猜想Kautz有向图K(d,k)的距离2-控制数γ2(K(d,k))= .     

反超图的着色理论

反超图及其上色数概念是由 Ｖｉｔａｌｙ　Ｉ,Ｖｏｌｏｓｈｉｎ在文献［２］中提出来的．本文给出了点对图的概念,再将反超图的着色理论和图的连通性理论结合起来,给出了个正则反超图上色数为３的充要条件,并在此基础上得到了上色数为３的４－正则反起图的边数的一个下界．     

有向图的Laplace谱半径

Laplace矩阵的谱半径一直是近年来谱图理论的研究热点.本文主要讨论有向图Laplace矩阵的谱半径,用顶点的出度和公共邻域数给出了谱半径上界,用图的最大出度给出了一些特殊图类谱半径的下界.     

论Ore图的泛连通性

符合Ore条件的简单图称为Ore图,Ore条件指图的两个不相邻的顶点的度数之和不小于图的顶点数。本文搞清了Ore图的泛连通性,同时得到了Ore图的点(边)泛圈性的结果,推广了Bondy的一个结论。     

完全图字典乘积的强半径和强直径

目前针对乘积图的强距离研究已经取得丰富成果,主要给出完全图字典乘积的强距离结果.基于字典乘积图与其因子图的关系,确定了两个完全图字典乘积的最小强半径;利用因子图与字典乘积图的顶点数的关系,得到完全图字典乘积的最大强直径和最大强半径的范围.除此之外,通过字典乘积的结合性,将字典乘积图的相关强距离结果进一步推广到多个完全图的字典乘积.     

强定向图的k-强距离

对强连通有向图D的一个非空顶点子集S,D中包含S的具有最少弧数的强连通有向子图称为S的Steiner子图,S的强Steiner距离d(S)等于S的Steiner子图的弧数. 如果|S|=k, 那么d(S)称为S的k-强距离. 对整数k≥2和强有向图D的顶点v,v的k-强离心率sek(v)为D中所有包含v的k个顶点的子集的k-强距离的最大值. D中顶点的最小k-强离心率称为D的k-强半径,记为sradk(D),最大k-强离心率称为D的k-强直径,记为sdiamk(D). 本文证明了,对于满足k+1≤r,d≤n的任意整数r,d,存在顶点数为n的强竞赛图T′和T″,使得sradk(T′)=r和sdiamk(T″)=d;进而给出了强定向图的k-强直径的一个上界.     

Kautz网络中的最小反馈点集

对简单有向图D=(V，E)，顶点子集F∈V，如果由V＼F导出的子图不含有向圈，则称F是D的反馈点集。点数最小的子集F称为最小反馈点集。最小的点数称为反馈数。本利用Kautz最小轨道的方法确定出了Kautz有向图K(d，k)反馈数的一个下界和上界。并且具体给出了当k≤3时的反馈数。     

二部图的距离k次方和问题（英文）

本文定义S_k(G)为G中所有点对之间距离的k次方之和.利用顶点划分的方法得到了直径为d的n顶点连通二部图S_k(G)的下界,并确定了达到下界所对应的的极图.     

三圈图的Harary指数

图G的Harary指数是指图G中所有顶点对间的距离倒数之和.三圈图是指边数等于顶点数加2的连通图.研究了三圈图的Harary指数,给出了所有三圈图中具有极大Harary指数的图的结构以及含有三个圈的三圈图中具有次大Harary指数的图的结构.     

一类三圈图的Wiener指数

图G的Wiener指数是指图G中所有顶点对间的距离之和,即W（G）=∑dc（u,u）,{u,u}CG其中de（u,u）表示G中顶点u,u之间的距离.三圈图是指边数与顶点数之差等于2的连通图,任意两个圈至多只有一个公共点的三圈图记为T_n~3.研究了三圈图T_n~3的Wiener指数,给出了其具有最小、次小Wiener指数的图结构.     

Distance and size in digraphs

We determine the maximum number of arcs in an Eulerian digraph of given order and diameter. Our bound generalises a classical result on the maximum number of edges of an undirected graph of given order and diameter by Ore (1968) and Homenko and Ostroverhii? (1970). We further determine the maximum size of a bipartite digraph of given order and radius.     

Some remarks on Arc-connectivity,vertex splitting,and orientation in graphs and digraphs

We apply proof techniques developed by L. Lovász and A. Frank to obtain several results on the arc-connectivity of graphs and digraphs. The first results concern the operation of splitting two arcs from a vertex of an Eulerian graph or digraph in such a way as to preserve local connectivity conditions. The final result is concerned with orienting the edges of a mixed graph (consisting of vertices, undirected edges, and directed arcs) in such a way that the resulting digraph is as arc-connected as possible.     

扩充竞赛图的(1,2)步竞争图

2011年Factor等人提出了有向图的(1,2)步竞争图的概念,并完全刻画了竞赛图的(1,2)步竞争图.设D=(V,A)是一个有向图.如果无向图G=(V,E)满足,V(G)=V(D)并且xy∈E(G)当且仅当D中存在顶点z≠x,y使得d_(D-y)(x,z)=1,d_(D-x)(y,z)≤2或者d_(D-x)(y,z)=1,d_(D-y)(x,z)≤2,那么称G为D的(1,2)步竞争图,记为C_(1,2)(D).本文主要刻画了扩充竞赛图的(1,2)步竞争图.     

A sharp upper bound for the spectral radius of a nonnegative matrix and applications

We obtain a sharp upper bound for the spectral radius of a nonnegative matrix. This result is used to present upper bounds for the adjacency spectral radius, the Laplacian spectral radius, the signless Laplacian spectral radius, the distance spectral radius, the distance Laplacian spectral radius, the distance signless Laplacian spectral radius of an undirected graph or a digraph. These results are new or generalize some known results.     

Enumeration of labelled chain graphs and labelled essential directed acyclic graphs

A chain graph is a digraph whose strong components are undirected graphs and a directed acyclic graph (ADG or DAG) G is essential if the Markov equivalence class of G consists of only one element. We provide recurrence relations for counting labelled chain graphs by the number of chain components and vertices; labelled essential DAGs by the number of vertices. The second one is a lower bound for the number of labelled essential graphs. The formula for labelled chain graphs can be extended in such a way, that allows us to count digraphs with two additional properties, which essential graphs have.     

A Vizing-type theorem for matching forests

A well-known Theorem of Vizing states that one can colour the edges of a graph by Δ+ colours, such that edges of the same colour form a matching. Here, Δ denotes the maximum degree of a vertex, and the maximum multiplicity of an edge in the graph. An analogue of this Theorem for directed graphs was proved by Frank. It states that one can colour the arcs of a digraph by Δ+ colours, such that arcs of the same colour form a branching. For a digraph, Δ denotes the maximum indegree of a vertex, and the maximum multiplicity of an arc. We prove a common generalization of the above two theorems concerning the colouring of mixed graphs (these are graphs having both directed and undirected edges) in such a way that edges of the same colour form a matching forest.     

Graphs having distance-n domination number half their order

For any positive integer n and any graph G a set D of vertices of G is a distance-n dominating set, if every vertex vV(G)−D has exactly distance n to at least one vertex in D. The distance-n domination number γ_=n(G) is the smallest number of vertices in any distance-n dominating set. If G is a graph of order p and each vertex in G has distance n to at least one vertex in G, then the distance-n domination number has the upper bound p/2 as Ore's upper bound on the classical domination number. In this paper, a characterization is given for graphs having distance-n domination number equal to half their order, when the diameter is greater or equal 2n−1. With this result we confirm a conjecture of Boland, Haynes, and Lawson.     

On Four-Connecting a Triconnected Graph

We consider the problem of finding a smallest set of edges whose addition four-connects a triconnected graph. This is a fundamental graph-theoretic problem that has applications in designing reliable networks and improving statistical database security. We present an O(n · α(m, n) + m)-time algorithm for four-connecting an undirected graph G that is triconnected by adding the smallest number of edges, where n and m are the number of vertices and edges in G, respectively, and α(m, n) is the inverse Ackermann function. This is the first polynomial time algorithm to solve this problem exactly.In deriving our algorithm, we present a new lower bound for the number of edges needed to four-connect a triconnected graph. The form of this lower bound is different from the form of the lower bound known for biconnectivity augmentation and triconnectivity augmentation. Our new lower bound applies for arbitrary k and gives a tighter lower bound than the one known earlier for the number of edges needed to k-connect a (k − 1)-connected graph. For k = 4, we show that this lower bound is tight by giving an efficient algorithm to find a set of edges whose size equals the new lower bound and whose addition four-connects the input triconnected graph.     

On the number of unique subgraphs

Entringer and Erdös introduced the concept of a unique subgraph of a given graph G and obtained a lower bound for the maximum number of unique subgraphs in any n-point graph, which we now improve.