有向图的拟强连通和超拟强连通性

Geller,F.和Harary,F.在文献[2]中对有向图的强连通,单侧连通和弱连通给出了几个性质定理。Berge,C.在[3]中曾定义了有向图的拟强连通。并对拟强连通与有向树的关系等给出了两个定理。本文对有向图的拟强连通和超拟强连通性得到了与[2]中相应的结果。     

极小和极大线有向图

F.Harary 和 R.Z.Norman 在文〔1〕中引入了线有向图.在文〔2〕中,Geller 和 Harary 给出了线有向图的几个充要条件,本文第一节指出其中有一个不够完备,并提出了改正意见.在文〔3〕中,Sumner 研究了极小线图,本文第二节将这个概念引入有向图,并得到有关充要条件.第三节引入了极大线有向图,也得到了一些结果.     

α2-独立数为2的有向图中的迹,路和圈

设α₂(D)=max{|X|:X?V(D)且D[X]不含有向2-圈}是有向图D的α₂ (D)-独立数.在文献[Proc.London Math.Soc.,42 (1981) 231-251]中,Thomassen构造了满足κ(D)=α(D)的非哈密尔顿有向图D,以此证明Chvátal-Erd?s定理在有向图情形下不能得到自然推广.Bang-Jensen和Thomassé提出如下猜想:每一个满足弧强连通度大于等于其独立数的有向图一定包含生成闭迹.对于满足弧强连通度大于等于其α2(D)-独立数的有向图是否包含生成迹这一问题,目前仍未解决.如果对于D中的任意两个顶点x和y,D包含生成(x,y)-迹,或者生成(y,x)-迹,则称有向图D是弱迹连通的.如果对于D中的任意两个顶点x和y,D既包含生成(x,y)-迹又包含生成(y,x)-迹,则称D是强迹连通的.本文在确定两个强连通有向图类M和H的基础上,研究了在满足α₂(D)=2条件下,有向图D的相关结果,并得到以下结论:(ⅰ) D是哈密尔顿的当且仅当D?M.(ⅱ) D是弱迹连通的.(...     

叉梯有向图在可定向曲面上的亏格多项式

虽然一些关于图的亏格分布的结果已经知道,但关于有向图的结果却很少.本文第二作者发现了计算图的嵌入多项式的联树法,这篇文章将此方法推广到计算有向图的嵌入多项式.得到了一类新的四正则叉梯有向图在可定向曲面上的亏格多项式.这些结果为解决Bonnington提出的第三个问题奠定了基础.     

DNA标号图和DNA计算

设$k\geq 2, 1\leq i \leq k$ 和 $\alpha \geq 1$是3个整数. 对任意一个由长为$k$的寡聚核苷酸组成的多重集, DNA标号图定义如下: 该多重集中的每个寡聚核苷酸作为一个顶点; 若一个顶点右端$i$个核苷酸与另一个顶点左端$i$个核苷酸相同, 则前一顶点控制后一顶点. 称有向图$D$是可$(k,i;\alpha)$标号的, 如果对$D$中的每个顶点$x$, 可设计一个$k$长的标号$(l_{1}(x),\ldots ,l_{k}(x)),$使得 对每一个$j\in \{1,\ldots,k\}$, $l_j(x)\in \{0,\ldots,\alpha-1\}$, 并且$(x,y)$是$D$中的一条弧当且仅当 $(l_{k-i+1}(x),\ldots,l_k(x))=(l_1(y),\ldots,l_i(y)).$ 由生物背景, 对一个有向图,若存在两个整数$k$和$i$, 使得它是可$(k,i;4)$标号的, 则它就是一个DNA标号图. 系统地研究了DNA标号图. 首先, 给出了它和一些已有图类之间的关系. 接着, 证明了对任意的DNA标号图,都存在一个正整数$i$, 使得它是可 $(2i,i;4)$标号的,这有利于DNA标号图的存储和操作. 此外, 还确定了最小的$i$, 并设计了一个多项式时间的算法对给定的DNA标号图进行$(2i,i;4)$标号. 最后, 在一个有$(2i,i;4)$标号的有向图上, 设计了一个DNA算法寻找给定两点间的所有路.     

关于有向图与超图的计数

1980年,M.Hegde和M.R.Sridharan沿用R.C.Read的计数方法,得到了标号偶有向图和偶超图的计数公式。我们推广了[1]的结果,得到了恰有2k个奇度点的p阶有向图和(p,q)有向图,恰有k个奇度点的p阶超图和(p,q)超图的计数式。本文所讨论的图均指标号图。     

非紧广义凸空间内的拟平衡问题

利用作者得到的一个新的不动点定理,在非紧广义凸空间内证明了拟平衡问题的几个新的平衡存在性定理.这些定理改进和推广了最近文献中许多已知结果.     

线有向图的幂敛指数

采用有向图的矩阵表示,得到了线有向图的幂敛指数和周期的有关结果.     

Brauer定理与Shemesh定理的改进

本文引进了矩阵有向图的κ—path覆盖概念，借此给出一个新的特征值分布定理，改进了经典的Brauer定理；进而给出一类矩阵的秩的下界，改进了Shemes定理。     

有向图n·C→3优美的进一步性质

本文在我们以往研究基础上,得到了有向图n·C→3优美的进一步性质:两个无交有向图n@C→3各自的公共顶点与一个新增加的顶点,分别用有向弧来连接,使该新增加顶点的出度为2或入度为2时,这样连接而得的有向图为优美图.     

Symmetric Graphs and Flag Graphs

 With any G-symmetric graph Γ admitting a nontrivial G-invariant partition , we may associate a natural “cross-sectional” geometry, namely the 1-design in which for and if and only if α is adjacent to at least one vertex in C, where and is the neighbourhood of B in the quotient graph of Γ with respect to . In a vast number of cases, the dual 1-design of contains no repeated blocks, that is, distinct vertices of B are incident in with distinct subsets of blocks of . The purpose of this paper is to give a general construction of such graphs, and then prove that it produces all of them. In particular, we show that such graphs can be reconstructed from and the induced action of G on . The construction reveals a close connection between such graphs and certain G-point-transitive and G-block-transitive 1-designs. By using this construction we give a characterization of G-symmetric graphs such that there is at most one edge between any two blocks of . This leads to, in a subsequent paper, a construction of G-symmetric graphs such that and each is incident in with vertices of B. The work was supported by a discovery-project grant from the Australian Research Council. Received April 24, 2001; in revised form October 9, 2002 Published online May 9, 2003     

双线性型图与交错型图不是完美图

本文证明了双线性型图与交错型图都不是完美图,从而解决了双线性型图与交错型图的完美图判别问题.     

门槛图与度极大图

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

原始图与三次图的可圈度

本文综述关于原始图与三次图的可圈度的近期结果并提出一些未解决的问题。     

Collapsible Graphs and Hamiltonicity of Line Graphs

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai (Combinatorics and Graph Theory, vol 95, World Scientific, Singapore, pp 53–69; Conjecture 8.6 of 1995) conjectured that every 3-edge connected and essentially 6-edge connected graph is collapsible. Denote D ₃(G) the set of vertices of degree 3 of graph G. For ${e = uv \in E(G)}$ , define d(e) = d(u) + d(v) ? 2 the edge degree of e, and ${\xi(G) = \min\{d(e) : e \in E(G)\}}$ . Denote by λ ^m (G) the m-restricted edge-connectivity of G. In this paper, we prove that a 3-edge-connected graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq7}$ is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq6}$ is collapsible; a 3-edge-connected graph with ${\xi(G)\geq6}$ , ${\lambda^2(G)\geq4}$ , and ${\lambda^3(G)\geq6}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq6}$ , and ${\lambda^3(G)\geq5}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected graph with ${\xi(G)\geq5}$ , and ${\lambda^2(G)\geq4}$ with at most 9 vertices of degree 3 is collapsible. As a corollary, we show that a 4-connected line graph L(G) with minimum degree at least 5 and ${|D_3(G)|\leq9}$ is Hamiltonian.     

Snarks,Hypohamiltonian Graphs and Non-Supereulerian Graphs

A graph G is hypohamiltonian if it is not Hamiltonian but for each \(v\in V(G)\), the graph \(G-v\) is Hamiltonian. A graph is supereulerian if it has a spanning Eulerian subgraph. A graph G is called collapsible if for every even subset \(R\subseteq V(G)\), there is a spanning connected subgraph H of G such that R is the set of vertices of odd degree in H. A graph is reduced if it has no nontrivial collapsible subgraphs. In this note, we first prove that all hypohamiltonian cubic graphs are reduced non-supereulerian graphs. Then we introduce an operation to construct graphs from hypohamiltonian cubic graphs such that the resulting graphs are 3-edge-connected non-supereulerian reduced graphs and cannot be contracted to a snark. This disproves two conjectures, one of which was first posed by Catlin et al. in [Congr. Num. 76:173–181, 1990] and in [J. Combin. Theory, Ser B 66:123–139, 1996], and was posed again by Li et al. in [Acta Math. Sin. English Ser 30(2):291–304, 2014] and by Yang in [Supereulerian graphs, hamiltonicity of graphs and several extremal problems in graphs, Ph. D. Dissertation, Université Paris-Sub, September 27, 2013], respectively, the other one was posed by Yang 2013.