共查询到20条相似文献,搜索用时 47 毫秒
1.
消去图、覆盖图和均匀图的若干结果 总被引: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相似文献
2.
孙荣国 《高校应用数学学报(A辑)》1994,(3):335-337
本文给出了书本图B2m的m种不同的相继标号和B4m+1的m种不同的相继标号。因而,书本图Bm是相继图的充分条件为:m>1且m≠(3mod4)。这一条件也是书本图Bm是协调图的充要条件。 相似文献
3.
两类满足A(H)=3的图 总被引:11,自引:0,他引:11
本文利用文[3]的方法给出了两类满足A(H)=3的图,从而肯定了满足A(H)=3的图是不唯一的。本文还给出了满足A(H)=3的最小图。 相似文献
4.
连通的顶点可迁图的色唯一性 总被引:3,自引:0,他引:3
本文给出从一个已知的顶点可迁的非色唯一图出发,构造无穷多个顶点可迁的非色唯一图的一种方法,据此给出若干类无穷多个连通的顶点可迁,但不是色唯一的图簇,从而进一步否定地回答了Chia在[1]中提出的问题. 相似文献
5.
6.
7.
8.
Alavi等人定义了一种关于图的新分解,即“升分解”并且猜想,任何有正条边的简单图可升分解。Hung-LinFu曾证明恰有(n+1/2)条边的完全二分图可升分解。本文得到了一个中的结论,证明了具有任何条边的完全二分图都可升分解。 相似文献
9.
Bubble-Sort图和Modified Bubble-Sort图是两类特殊的Cayley图,由于其在网络构建中的应用而受到广泛关注.本文完全确定了这两类图的自同构群. 相似文献
10.
图的spread定义为图的邻接矩阵的最大特征值与最小特征值的差.本文确定了n(n≥84)顶点四圈图中spread最大的唯一的图. 相似文献
11.
Let n,k and l be integers with 1 ≤ k < l ≤ n-1.The set-inclusion graph G(n,k,l) is the graph whose vertex set consists of all k-andl-subsets of[n]={1,2,...,n},where two distinct vertices are adjacent if one of them is contained in the other.In this paper,we determine the spectrum and automorphism group of G(n,k,l). 相似文献
12.
Let be a graph with diameter d 2. Recall is 1-homogeneous (in the sense of Nomura) whenever for every edge xy of the distance partition{{z V() | (z, y) = i, (x, z) = j} | 0 i, j d}is equitable and its parameters do not depend on the edge xy. Let be 1-homogeneous. Then is distance-regular and also locally strongly regular with parameters (v,k,,), where v = k, k = a
1, (v – k – 1) = k(k – 1 – ) and c
2 + 1, since a -graph is a regular graph with valency . If c
2 = + 1 and c
2 1, then is a Terwilliger graph, i.e., all the -graphs of are complete. In [11] we classified the Terwilliger 1-homogeneous graphs with c
2 2 and obtained that there are only three such examples. In this article we consider the case c
2 = + 2 3, i.e., the case when the -graphs of are the Cocktail Party graphs, and obtain that either = 0, = 2 or is one of the following graphs: (i) a Johnson graph J(2m, m) with m 2, (ii) a folded Johnson graph J¯(4m, 2m) with m 3, (iii) a halved m-cube with m 4, (iv) a folded halved (2m)-cube with m 5, (v) a Cocktail Party graph K
m × 2 with m 3, (vi) the Schläfli graph, (vii) the Gosset graph. 相似文献
13.
关于《关于Ramsey数下界的部分结果》的注 总被引:1,自引:0,他引:1
张忠辅 《数学的实践与认识》2002,32(4):686
本文用反例 ,说明了 [1 ]中 R( l,s+ t-2 ) R( l,s) + R( l,t) -1是错的 相似文献
14.
J. Plávka 《Mathematical Methods of Operations Research》1992,36(5):417-422
Let twon×n matrices be given, namely a real matrixA=(aij) and a (0, 1)-matrixT=(tij). For a cyclic permutation=(i
1,i
2,...,i
k) of a subset of N={1, 2, ..., n} we define A;T(), the cost-to-time ratio weight of, as
. This paper presents an O(n3) algorithm for finding (A;T)=max A;T(), the maximum cost-to-time ratio weight of the matricesA andT. Moreover a generalised eigenproblem is proposed. 相似文献
15.
The independent domination number i(G) (independent number (G)) is the minimum (maximum) cardinality among all maximal independent sets of G. Haviland (1995) conjectured that any connected regular graph G of order n and degree 1/2n satisfies i(G) 2n/3 1/2. For 1 k l m, the subset graph S
m
(k, l) is the bipartite graph whose vertices are the k- and l-subsets of an m element ground set where two vertices are adjacent if and only if one subset is contained in the other. In this paper, we give a sharp upper bound for i(S
m
(k, l)) and prove that if k + l = m then Havilands conjecture holds for the subset graph S
m
(k, l). Furthermore, we give the exact value of (S
m
(k, l)).This work was supported by National Natural Sciences Foundation of China (19871036). 相似文献
16.
Robert W. Baddeley 《Journal of Algebraic Combinatorics》1993,2(3):215-237
The paper addresses a part of the problem of classifying all 2-arc transitive graphs: namely, that of finding all groups acting 2-arc transitively on finite connected graphs such that there exists a minimal normal subgroup that is nonabelian and regular on vertices. A construction is given for such groups, together with the associated graphs, in terms of the following ingredients: a nonabelian simple group T, a permutation group P acting 2-transitively on a set , and a map F : Tsuch that x = x
–1 for all x
F() and such that Tis generated by F(). Conversely we show that all such groups and graphs arise in this way. Necessary and sufficient conditions are found for the construction to yield groups that are permutation equivalent in their action on the vertices of the associated graphs (which are consequently isomorphic). The different types of groups arising are discussed and various examples given. 相似文献
17.
The interval graph completion problem of a graph G includes two class problems: the profile problem and the pathwidth problem, denoted as P(G) and PW(G) respectively, where the profile problem is to find an interval supergraph with the smallest possible number of edges; the pathwidth problem is to find an interval supergraph with the smallest possible cliquesize. These two class problems have important applications to numerical algebra, VLSI-layout and algorithm graph theory respectively; And they are known to be NP-complete for general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the exact solutions of the profile and the pathwidth of the complete multipartite Graph Kn1,n2,…,nr(r≥2) are determined. 相似文献
18.
19.
Bohdan Zelinka 《Czechoslovak Mathematical Journal》2003,53(3):627-629
One of numerical invariants concerning domination in graphs is the k-subdomination number
of a graph G. A conjecture concerning it was expressed by J.H. Hattingh, namely that for any connected graph G with n vertices and any k with
the inequality
holds. This paper presents a simple counterexample which disproves this conjecture. This counterexample is the graph of the three-dimensional cube and k = 5. 相似文献
20.
完全二部图广义Mycielski图的邻点可区别全色数与邻强边色数 总被引:6,自引:1,他引:5
得到了完全二部图Km,n的广义Mycielski图Ml(Km,n),当(l≥1,n≥m≥2)时的邻点可区别全色数与邻强边色数. 相似文献