共查询到19条相似文献,搜索用时 93 毫秒
1.
应用矩阵的初等变换得到了完全五部图的 Seidel 多项式,并给出了完全五部图是S-整图的一个充分必要条件。进一步刻画了完全正则五部图和两类特殊完全五部图的Seidel谱。 相似文献
2.
卢世芳 《数学的实践与认识》2014,(5)
研究Laplace整图的存在性问题,通过研究完全多部图K_(a_1n_1,a_2n_2,…a_sn_s)的Laplace特征多项式,得到所有完全多部图K_(a_1n_1,a_2n_2,…a_sn_s)都是拉普拉斯整图. 相似文献
3.
设图G是一个简单图,图G的补图记为^-G,如果G的谱都是整数,就称G是整谱图.鸡尾酒会图CP(n)=K2n-nK2(K2n是2n阶完全图)和完全图Kα都是整谱图.本文确定了图类^-αKα∪βCP(b)中的所有整谱图. 相似文献
4.
5.
图类aKa,a\βCP(b)中的整谱图 总被引:1,自引:0,他引:1
设图G是一个简单图,图G的补图记为G,如果G的谱都是整数.就称G是整谱图.鸡尾酒会图CP(n)=K2n-nK2(K2n是2n阶完全图)和完全二部图K…都是整谱图.确定了图类 aKa,a∪βCP中的所有的整谱图. 相似文献
6.
7.
消去图、覆盖图和均匀图的若干结果 总被引:2,自引:0,他引:2
设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g相似文献
8.
用P(G,λ)表示图G的色多项式.若对任意图H,当P(H,λ)=P(G,λ)时都有H和G同构,则称图G是色唯一的.给出了以下结果:m≥2且k≥0时,完全三部图K(m,m,m+k)是色唯一的;m≥2且m+1>k≥0时,完全三部图K(m,m+1,m+k)是色唯一的. 相似文献
9.
10.
11.
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. 相似文献
12.
Larry D Gassman R.C Entringer John R Gilbert Stephen A Lonz Wayne Vucenic 《Journal of Combinatorial Theory, Series B》1975,19(3):214-238
Ore defined a graph to be geodetic if and only if there is a unique shortest path between two points, and posed the problem of characterizing such graphs. Here this problem is studied in the context of oriented graphs and such geodetic orientations are characterized first for complete graphs (geodetic tournaments), then for complete bipartite and complete tripartite graphs, and finally for complete k-partite graphs. 相似文献
13.
14.
On bipartite zero-divisor graphs 总被引:1,自引:0,他引:1
A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3. 相似文献
15.
An edge dominating set of a graph is a set of edgesD such that every edge not inD is adjacent to an edge inD. An edge domatic partition of a graph G =(V, E) is a collection of pairwise disjoint edge dominating sets of G whose union isE. The maximum size of an edge domatic partition of G is called the edge domatic number of G. In this paper we study the edge domatic numbers of completen-partite graphs. In particular, we give exact values for the edge domatic numbers of complete 3-partite graphs and balanced complete n-partite graphs with oddn. 相似文献
16.
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. 相似文献
17.
Curtis R. Cook 《Discrete Mathematics》1974,8(4):305-311
A graph G is m-partite if its points can be partitioned into m subsets V1,…,Vm such that every line joins a point in Vi with a point in Vj, i ≠ j. A complete m-partite graph contains every line joining Vi with Vj. A complete graph Kp has every pair of its p points adjacent. The nth interchange graph In(G) of G is a graph whose points can be identified with the Kn+1's of G such that two points are adjacent whenever the corresponding Kn+1's have a Kn in common.Interchange graphs of complete 2-partite and 3-partite graphs have been characterized, but interchange graphs of complete m-partite graphs for m > 3 do not seem to have been investigated. The main result of this paper is two characterizations of interchange graphs of complete m-partite graphs for m ≥ 2. 相似文献
18.
Aart Blokhuis Andries E. Brouwer Willem H. Haemers 《Designs, Codes and Cryptography》2007,44(1-3):293-305
We give some necessary conditions for a graph to be 3-chromatic in terms of the spectrum of the adjacency matrix. For all known distance-regular graphs it is determined whether they are 3-chromatic. A start is made with the classification of 3-chromatic distance-regular graphs, and it is shown that such graphs, if not complete 3-partite, must have λ ≤ 1. 相似文献
19.
Richard Hammack 《Journal of Graph Theory》1999,32(2):160-170
The cyclicity of a graph is the largest integer n for which the graph is contractible to the cycle on n vertices. By analyzing the cycle space of a graph, we establish upper and lower bounds on cyclicity. These bounds facilitate the computation of cyclicity for several classes of graphs, including chordal graphs, complete n-partite graphs, n-cubes, products of trees and cycles, and planar graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 160–170, 1999 相似文献