正P-矩阵的逆零完成问题(英文)

本文基于不完备P-矩阵的1-通弦图和1-通弦块图的完成问题,获得了不完备正P-矩阵在一定条件下的k-通弦图和k-通弦块图的完成,同时解决了不完备正P-矩阵在k-通弦图和k-通弦块图下的逆零完成问题(k为大于1的整数).     

有向树的部分逆M矩阵完备及其算法设计

1 引言 M矩阵是具有非正非对角元且其逆是非负矩阵的一类矩阵．逆M矩阵是逆为M矩阵的一类非负矩阵．部分矩阵是指一个矩阵中一些元已定,其余未定元还可以自由选择的矩阵．如果在一个部分矩阵中,其每个已定的主子矩阵均为逆M矩阵并且所有已定元均是非负的,称这个部分矩阵是一个部分逆M矩阵．一个部分逆M矩阵的完备式是对     

逆M矩阵模型的完备及其算法设计

1 引 言 M矩阵是具有非负对角元和非正非对角元且其逆是非负矩阵的一类矩阵.逆M矩阵即逆为M矩阵的一类非负矩阵.逆M矩阵在物理学,生物学,控制理论,神经网络方面有着重要的应用.所以对逆M矩阵的研究一直在持续不断的进行.一个“部分矩阵”是指在一个矩阵中,一些元素已经给定了,而另一些元素待定的矩阵.而一个矩阵的完     

带弦的圈是协调图

称具有ｅ条边的简单图Ｇ为协调图，若存在由Ｇ的顶点集到模ｅ的整数群Ｚｅ的一个单射ｈ，使得导出映射ｈ＾＊：ｈ＾＊（ｕｖ）≡ｈ（ｕ）＋ｈ（ｖ）（ｍｏｄ ｅ）是一个由Ｇ的边集到Ｚｅ的双射，带弦的圈Ｃ′ｎ是由含ｎ个顶点的圈Ｃｎ上添一条连结两个不相邻顶点的边而得到的图。本文中证明了，除了ｎ＝６且弦端点在Ｃｎ上的距离为２的情况外，所有带弦的圈都是协调图。     

分支数≤7时S^2NS有向图的禁用子图刻划

实方阵A称为强符号非异阵（S~2NS阵）,若任一与A符号模式相同的矩阵非异且其逆的符号模式也一致。若一个有向图是某一S~2NS阵对应赋号有向图的基础有向图,称为S~2NS有向图。本文用禁用子图形式给出了分支数≤7时有向图成为S~2NS有向图的刻划,同时部分地解决了[2]和[4]中提出的问题。     

回路图的部分逆M矩阵完备问题

<正>1引言M矩阵是具有非正非对角元且其逆是非负矩阵的一类矩阵.1977年wmoughby~([1])提出把非负矩阵的逆是M矩阵的这一类矩阵定义为逆M矩阵.逆M矩阵在生物学、经济学、智能科学、计算方法等许多科学中都具有重要应用,许多实际问题的结论都可以归结到逆M矩阵的判定上,因此研究逆M矩阵的判定方法,成为当今矩阵理论研究中的一个热点,而利用图论知识研究逆M矩阵完备问题是逆M矩阵研究中的一个重要方     

三对角逆M矩阵的判定

1、引言 三对角逆M矩阵是指同时为三对角矩阵和逆M矩阵的一类特殊矩阵．文用图论方法探讨三对角逆M矩阵结构,给出了三对角矩阵为逆M矩阵的充分必要条件．此条件提供了判定三对角矩阵是逆M矩阵的方法,但较复杂．文讨论了这类矩阵在Hadamard积下的封闭性．由于三对角逆M矩阵在理论和应用上都有一定价值,所以,寻求一种简单而实用的判定方法是必要的．本文通过对这类矩阵结构特点的研究找到了这样一种方法．同时,由此证明了这类矩阵在Hadamard积下的封闭性．     

Fan型条件对图的匹配的影响(英文)

设G是顶点数为2n且至多含有2(n-c)个奇分支的简单图(1≤c≤n).若不存在G的两个距离为2的顶点,其度均小于c-1,则G的边独立数至少为c,除非G含一类明显的禁用导出子图.特别,我们给出了Fan(-1)-型图含有1-因子的充要条件.     

最大度不小于6的伪-Halin图的完备色数

设G为2-连通平面图,若存在G的面f₀,其中f₀的边界构成的圈上无弦且V（f₀）中的点的度至少为3,使得在G中去掉f₀边界上的所有边后得到的图为除V（f₀）中的点外度不小于3的树T,则称G为伪-Halin图;若V（f₀）中的点全为3度点,则称G为Halin-图.本文研究了这类图的完备色数,并证明了对△（G）≥ 6的伪-Halin图 G有 X_C（C）=△（G）+1.其中△（G）和X_C（G）分别表示G的最大度和完备色数.     

弦图的最大权强独立集

一、 引言 本文中未加说明的图论术语来自文献[1]。图G=(V,E)称为弦图,如果G的任何长度大于3的圈都有弦,或者等价地,任何长度大于3的圈都不会是G的点导出子图。本文中,子图总是指点导出子图,点子集S导出的G的子图记为G[S]。团是指完备子图,通常用它的点集来表示。如果图G的每个点v都带有点权w(v),则点子集S的权定义为S中点的权的和。     

超欧拉扩展有向图

A digraph D is supereulerian if D has a spanning eulerian subdigraph. BangJensen and Thomass′e conjectured that if the arc-strong connectivity λ(D) of a digraph D is not less than the independence number α(D), then D is supereulerian. In this paper, we prove that if D is an extended cycle, an extended hamiltonian digraph, an arc-locally semicomplete digraph, an extended arc-locally semicomplete digraph, an extension of two kinds of eulerian digraph, a hypo-semicomplete digraph or an extended hypo-semicomplete digraph satisfyingλ(D) ≥α(D), then D is supereulerian.     

有向跳图的生成欧拉子有向图

一个有向多重图D的跳图$J(D)$是一个顶点集为$D$的弧集,其中$(a,b)$是$J(D)$的一条弧当且仅当存在有向多重图$D$中的顶点$u_1$, $v_1$, $u_2$, $v_2$,使得$a=(u_1,v_1)$, $b=(u_2,v_2)$ 并且$v_1\neq u_2$.本文刻画了有向多重图类$\mathcal{H}_1$和$\mathcal{H}_2$,并证明了一个有向多重图$D$的跳图$J(D)$是强连通的当且仅当$D\not\in \mathcal{H}_1$.特别地, $J(D)$是弱连通的当且仅当$D\not\in \mathcal{H}_2$.进一步, 得到以下结果: (i) 存在有向多重图类$\mathcal{D}$使得有向多重图$D$的强连通跳图$J(D)$是强迹连通的当且仅当$D\not\in\mathcal{D}$. (ii) 每一个有向多重图$D$的强连通跳图$J(D)$是弱迹连通的,因此是超欧拉的. (iii) 每一个有向多重图D的弱连通跳图$J(D)$含有生成迹.     

有向P2-路图的结构性质

一个有向图D的有向Pk-路图Pk(D)是通过把D中的所有有向k长路作为点集;两点u= x1x2…xk+1,v=y1y2…yk+1之间有弧uv当xi=yi-1,i=2,3,…,k+1.明显地,当k=1时Pk(D)就是通常的有向线图L(D).在[1,2]中,P2-路图得到完整刻画.在[3]中,Broersma等人研究了有向...     

全有向图的幂敛指数

设D为有向图，T（D）为D的全有向图（Total-digraph),k(D)和p(D)分别为D的幂敛指数（Index of convergence)与周期（Period)，本文证明了。1，对任意非平凡有向图D,p(T(D))=1,k(T(D))≤max{2p(D)-1,2K(D) 1}，特别地，当D为本原有向图时，k(T(D))≤k(D) 1，当D不含有向圈时，k(T(D))=2k(D)-1；当D为有向圈Cn时，k(T(D))=2n-1.2。对任意非平凡强连通图D,k(T(D))≥Diam(D) 1。我们还证明了以上界是不可改进的最好界。     

有向图3C2p的优美性

图论是数学的一个分支,特别是离散数学的一个重要分支,它在物理、化学、天文、地理、生物学,尤其是在计算机科学中有着非常广泛的应用．图的标号问题是图论中极有趣的一个研究课题,有着较好的研究价值和广阔的应用背景．图的一个顶点标号是顶点集合到非负整数集合的映射,而边标号是边集合到非负整数集合的映射,根据对映射的不同要求,产生了各种各样的图的标号问题,有向图的优美标号是其中的一类．用G表示有n个顶点的有向圈,mCn表示m个无公共顶点的有向圈G之并,本文研究了有向图mG,的优美性,利用搜索图的标号的算法与数学证明相结合的方法,证实了有向图3Cn为优美图,其中n=2p,P为任意正整数．     

Every cycle-connected multipartite tournament has a universal arc

A digraph D is cycle-connected if for every pair of vertices u,v∈V(D) there exists a directed cycle in D containing both u and v. In 1999, Ádám [A. Ádám, On some cyclic connectivity properties of directed graphs, Acta Cybernet. 14 (1) (1999) 1-12] posed the following problem. Let D be a cycle-connected digraph. Does there exist a universal arc in D, i.e., an arc e∈A(D) such that for every vertex w∈V(D) there is a directed cycle in D containing both e and w?A c-partite or multipartite tournament is an orientation of a complete c-partite graph. Recently, Hubenko [A. Hubenko, On a cyclic connectivity property of directed graphs, Discrete Math. 308 (2008) 1018-1024] proved that each cycle-connected bipartite tournament has a universal arc. As an extension of this result, we show in this note that each cycle-connected multipartite tournament has a universal arc.     

Minimum orders of eulerian oriented digraphs with given diameter

A digraph D is oriented if it does not contain 2-cycles.If an oriented digraph D has a directed eulerian path,it is an oriented eulerian digraph.In this paper,when an oriented eulerian digraph D has minimum out-degree 2 and a diameter d,we find the minimum order of D.In addition,when D is 2-regular with diameter 4m(m ≥ 2),we classify the extremal cases.     

Superpure digraph designs

A digraph design is a decomposition of a complete (symmetric) digraph into copies of pre‐specified digraphs. Well‐known examples for digraph designs are Mendelsohn designs, directed designs or orthogonal directed covers. A digraph design is superpure if any two of the subdigraphs in the decomposition have no more than two vertices in common. We give an asymptotic existence theorem for superpure digraph designs, which is a variation of an earlier result of Lamken and Wilson J Combin Theory Ser A 89: 149–200, 2000. As an immediate consequence, we obtain new results for supersimple designs and pure perfect Mendelsohn designs. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 239–255, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10013     

Finding coherent cyclic orders in strong digraphs

A cyclic order in the vertex set of a digraph is said to be coherent if any arc is contained in a directed cycle whose winding number is one. This notion plays a key role in the proof by Bessy and Thomassé (2004) of a conjecture of Gallai (1964) on covering the vertex set by directed cycles. This paper presents an efficient algorithm for finding a coherent cyclic order in a strongly connected digraph, based on a theorem of Knuth (1974). With the aid of ear decomposition, the algorithm runs in O(nm) time, where n is the number of vertices and m is the number of arcs. This is as fast as testing if a given cyclic order is coherent.     

Locally-finite connected-homogeneous digraphs

A digraph is connected-homogeneous if any isomorphism between finite connected induced subdigraphs extends to an automorphism of the digraph. We consider locally-finite connected-homogeneous digraphs with more than one end. In the case that the digraph embeds a triangle we give a complete classification, obtaining a family of tree-like graphs constructed by gluing together directed triangles. In the triangle-free case we show that these digraphs are highly arc-transitive. We give a classification in the two-ended case, showing that all examples arise from a simple construction given by gluing along a directed line copies of some fixed finite directed complete bipartite graph. When the digraph has infinitely many ends we show that the descendants of a vertex form a tree, and the reachability graph (which is one of the basic building blocks of the digraph) is one of: an even cycle, a complete bipartite graph, the complement of a perfect matching, or an infinite semiregular tree. We give examples showing that each of these possibilities is realised as the reachability graph of some connected-homogeneous digraph, and in the process we obtain a new family of highly arc-transitive digraphs without property Z.