共查询到18条相似文献,搜索用时 109 毫秒
1.
在他人研究完全多部图的邻接谱的基础上,对整完全多部图的Seidel多项式进行研究分析,以期得到完全六部图G是S-整图的充要条件.从讨论完全六部图的Seidel多项式入手,应用矩阵行初等变换的方法给出完全六部图G是S-整图的充要条件. 相似文献
2.
3.
图G的交叉数是刻画图的非平面性的一个重要参数.它是指图G在平面上的所有画法中边与边之间交叉数目的最小值.确定具体图类的交叉数是图的交叉数问题中一个经典的研究方向.Zarankiewicz于1954年提出了完全二部图交叉数的猜想:■.1971年,Kleitman证明了当min{m,n}≤6时,上式成立.由于其难度,完全二部图交叉数的研究进展是较缓慢的.至今,完全二部图K7,n(n≥11)的交叉数都还未确定.然而,我们发现研究近完全二部图的交叉数可了解在完全二部图中加边与完全二部图交叉数的增长程度之间的关系.因此,为了促进完全二部图交叉数的研究,本文借助旋系与交叉数之间的关系、图的结构性质以及图的顶点度局部修改法确定了五个近完全二部图的交叉数. 相似文献
4.
5.
利用Kleitman D J给出的完全二部图的的交叉数cr(_(5,n))=Z(5,n)的结果,分别得到了联图G_(12)∨P_n,G_(15)∨P_n,G_(18)∨P_n的交叉数.同时,给出了目前已知的所有五阶图与路的联图交叉数情况. 相似文献
6.
确定图的交叉数是NP-完全问题.目前有关完全二部图与星图的积图的交叉数结果并不多.引入了一些新的收缩技巧,建立了积图K3,3□Sn与完全三部图K3,3□Sn之间的交叉数关系.从而,为进一步完全确定积图K3,3□Sn的交叉数提供了一条新途径. 相似文献
7.
8.
确定图的交叉数是NP-完全问题. 目前有关完全二部图与星图的积图的交叉数结果并不多. 引入了一些新的收缩技巧, 建立了积图K_{3,3}\square S_n与完全三部图K_{3,3,n}之间的交叉数关系. 从而, 为进一步完全确定积图K_{3,3}\square S_n的交叉数提供了一条新途径. 相似文献
9.
对非负整数序列π=(d1,d2……,dn),0≤di≤n-1,本分别给出了它蕴含导出子图为几乎处处完全图,完全图去掉一个Hamilton圈的边,完全k-部图可图(即蕴含aw^1,Aw^2和Ar,r2…,rk-可图)的判别准则。 相似文献
10.
11.
A graph is S-integral (or Seidel integral) if the spectrum of its Seidel matrix consists entirely of integers. In this paper, we give a sufficient and necessary condition for complete r-partite graphs to be S-integral, from which we construct infinitely many new classes of S-integral graphs. We also present an upper bound and a lower bound for the smallest S-eigenvalue (or Seidel eigenvalue) of a complete multipartite graph. 相似文献
12.
A graph is Q-integral if the spectrum of its signless Laplacian matrix consists entirely of integers. In their study of Q-integral complete multipartite graphs, [Zhao et al., Q-integral complete r-partite graphs, Linear Algebra Appl. 438 (2013) 1067–1077] posed two questions on the existence of such graphs. We resolve these questions and present some further results characterizing particular classes of Q-integral complete multipartite graphs. 相似文献
13.
Akos Seress 《Designs, Codes and Cryptography》2000,21(1-3):205-208
Seidel switching is an operation on graphs G satisfyingcertain regularity properties so that the resulting graph Hhas the same spectrum as G. If G issimple then the complement of G and the complementof H are also cospectral. We use a generalizationof Seidel switching to construct exponentially large familiesof cospectral graphs with cospectral complements. 相似文献
14.
Lutz Volkmann 《Discrete Mathematics》2007,307(24):3097-3129
A multipartite or c-partite tournament is an orientation of a complete c-partite graph. In this survey we mainly describe results on directed cycles and paths in strongly connected c-partite tournaments for c?3. In addition, we include about 40 open problems and conjectures. 相似文献
15.
Rosenfeld (1971) proved that the Total Colouring Conjecture holds for balanced complete r-partite graphs. Bermond (1974) determined the exact total chromatic number of every balanced complete r-partite graph. Rosenfeld's result had been generalized recently to complete r-partite graphs by Yap (1989). The main result of this paper is to prove that the total chromatic number of every complete r-partite graph G of odd order is Δ (G) + 1. This result gives a partial generalization of Bermond's theorem. 相似文献
16.
An n-partite tournament is an orientation of a complete n-partite graph. An n-partite tournament is a tournament, if it contains exactly one vertex in each partite set. Douglas, Proc. London Math. Soc.
21 (1970) 716–730, obtained a characterization of strongly connected tournaments with exactly one Hamilton cycle (i.e., n-cycle). For n≥3, we characterize strongly connected n-partite tournaments that are not tournaments with exactly one n-cycle. For n≥5, we enumerate such non-isomorphic n-partite tournaments. 相似文献
17.
Lutz Volkmann 《Discrete Mathematics》2006,306(21):2724-2732
A tournament is an orientation of a complete graph, and in general a multipartite or c-partite tournament is an orientation of a complete c-partite graph.For c?2 we prove that a regular c-partite tournament with r?2 vertices in each partite set contains a directed path with exactly two vertices from each partite set. Furthermore, if c?4, then we will show that almost all regular c-partite tournaments D contain a directed path with exactly r-s vertices from each partite set for each given integer s∈N, if r is the cardinality of each partite set of D. Some related results are also presented. 相似文献
18.
In this article, we give the maximum number of arc-disjoint arborescences in a tournament or an oriented complete r-partite graph by means of the indegrees of its vertices. 相似文献