共查询到20条相似文献,搜索用时 78 毫秒
1.
利用轮子图构造出一类图,证明了这类图都是点传递但边不传递的正则图,并证明了通过覆盖的方法,可以使一类2m2(m>3,m为正整数)阶非边传递图变成对称图,这类对称图实际上是亚循环图. 相似文献
2.
3.
本文给出了Frobenius群Z_(2n~2 2n 1)■Z_4的一类四度Frobenius图.沿用方、李和Praeger的方法,计算出了这一类图的直径和型(定理3.2). 相似文献
4.
Alspach证明了正则竞赛图具有弧泛回路的性质。本文将指出有更大一类竞赛图也具有弧泛回路的性质。并且正则竞赛图也显然属于这一类竞赛图。这类竞赛图满足两个条件:弧三回路和|T|≤4k-3(k为竞赛图T的最小出、入度)。 相似文献
5.
《数学的实践与认识》2013,(13)
首先证明了关于一般图的多色Ramsey数的一个下界,该下界是一类星图对完全图的多色Ramsey数的精确下界;其次证明了关于星图对完全图的多色Ramsey数的上界,该上界是一类星图对完全图的多色RamSey数的精确上界;最后证明关于树图对完全图的多色Ramsey数的上界. 相似文献
6.
本文研究了连通图的Laplacian特征值,利用图的Laplacian矩阵的特征多项式的行列式表示式,对存在两个不同顶点,但有相同邻集的一类图,得到了一个Laplacian特征值,并给出了它的应用. 相似文献
7.
8.
9.
研究了基于n阶二部图和s阶完全图构造的一个图类,得到了该图类的无符号拉普拉斯最小特征值(即最小Q-特征值)的一个可达上界为s.基于此,对于任意给定的正整数s和正偶数n,构造了最小Q-特征值为s的一类n+s阶图.另外,对于任意给定的最小度δ和阶数n,在满足2≤δ≤n-1/2条件下,构造了最小Q-特征值为δ-1的一类n阶图. 相似文献
10.
11.
Bubble-Sort图和Modified Bubble-Sort图是两类特殊的Cayley图,由于其在网络构建中的应用而受到广泛关注.本文完全确定了这两类图的自同构群. 相似文献
12.
13.
图X称为边正则图,若X的自同构群Aut(X)在X的边集上的作用是正则的.本文考察了三度边正则图与四度Cayley图的关系,给出了一个由四度Cayley图构造三度边正则图的方法,并且构造了边正则图的三个无限族. 相似文献
14.
15.
Cover-Incomparability Graphs of Posets 总被引:1,自引:1,他引:0
Boštjan Brešar Manoj Changat Sandi Klavžar Matjaž Kovše Joseph Mathews Antony Mathews 《Order》2008,25(4):335-347
Cover-incomparability graphs (C-I graphs, for short) are introduced, whose edge-set is the union of edge-sets of the incomparability
and the cover graph of a poset. Posets whose C-I graphs are chordal (resp. distance-hereditary, Ptolemaic) are characterized
in terms of forbidden isometric subposets, and a general approach for studying C-I graphs is proposed. Several open problems
are also stated. 相似文献
16.
17.
Equistable graphs are graphs admitting positive weights on vertices such that a subset of vertices is a maximal stable set if and only if it is of total weight 1. Strongly equistable graphs are graphs such that for every and every nonempty subset T of vertices that is not a maximal stable set, there exist positive vertex weights assigning weight 1 to every maximal stable set such that the total weight of T does not equal c . General partition graphs are the intersection graphs of set systems over a finite ground set U such that every maximal stable set of the graph corresponds to a partition of U . General partition graphs are exactly the graphs every edge of which is contained in a strong clique. In 1994, Mahadev, Peled, and Sun proved that every strongly equistable graph is equistable, and conjectured that the converse holds as well. In 2009, Orlin proved that every general partition graph is equistable, and conjectured that the converse holds as well. Orlin's conjecture, if true, would imply the conjecture due to Mahadev, Peled, and Sun. An “intermediate” conjecture, posed by Miklavi? and Milani? in 2011, states that every equistable graph has a strong clique. The above conjectures have been verified for several graph classes. We introduce the notion of equistarable graphs and based on it construct counterexamples to all three conjectures within the class of complements of line graphs of triangle‐free graphs. We also show that not all strongly equistable graphs are general partition. 相似文献
18.
A clique in a graph is strong if it intersects all maximal independent sets. A graph is localizable if it has a partition of the vertex set into strong cliques. Localizable graphs were introduced by Yamashita and Kameda in 1999 and form a rich class of well-covered graphs that coincides with the class of well-covered graphs within the class of perfect graphs. In this paper, we give several equivalent formulations of the property of localizability and develop polynomially testable characterizations of localizable graphs within three non-perfect graph classes: triangle-free graphs, -free graphs, and line graphs. Furthermore, we use localizable graphs to construct an infinite family of counterexamples to a conjecture due to Zaare-Nahandi about -partite well-covered graphs having all maximal cliques of size . 相似文献
19.
The pre-coloring extension problem consists, given a graph G and a set of nodes to which some colors are already assigned, in finding a coloring of G with the minimum number of colors which respects the pre-coloring assignment. This can be reduced to the usual coloring problem
on a certain contracted graph. We prove that pre-coloring extension is polynomial for complements of Meyniel graphs. We answer
a question of Hujter and Tuza by showing that “PrExt perfect” graphs are exactly the co-Meyniel graphs, which also generalizes
results of Hujter and Tuza and of Hertz. Moreover we show that, given a co-Meyniel graph, the corresponding contracted graph
belongs to a restricted class of perfect graphs (“co-Artemis” graphs, which are “co-perfectly contractile” graphs), whose
perfectness is easier to establish than the strong perfect graph theorem. However, the polynomiality of our algorithm still
depends on the ellipsoid method for coloring perfect graphs.
C.N.R.S.
Final version received: January, 2007 相似文献
20.
René van Bevern Robert Bredereck Laurent Bulteau Jiehua Chen Vincent Froese Rolf Niedermeier Gerhard J. Woeginger 《Journal of Graph Theory》2017,85(2):297-335
The partition of graphs into “nice” subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same‐size stars, a problem known to be NP‐complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial‐time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP‐complete cases, for example, on grid graphs and chordal graphs. 相似文献