排序方式: 共有39条查询结果,搜索用时 46 毫秒
1.
2.
Va?ek Chv��tal 《Graphs and Combinatorics》2011,27(2):171-175
We show that the method of counting closed walks in strongly regular graphs rules out no parameter sets other than those ruled
out by the method of counting eigenvalue multiplicities. 相似文献
3.
Abull is the (self-complementary) graph with verticesa, b, c, d, e and edgesab, ac, bc, bd, ce; a graphG is calledBerge if neitherG not its complement contains a chordless cycle whose length is odd and at least five. We prove that bull-free Berge graphs are perfect; a part of our argument relies on a new property of minimal imperfect graphs.This work was done while both authors were at the School of Computer Science, McGill University; support by NSERC is gratefully acknowledged. 相似文献
4.
The vertex-coloring group and the full automorphism group of an n-colorable graph are independent if and only if n is an integer ≥ 3. 相似文献
5.
6.
We prove that there is a function h(k) such that every undirected graph G admits an orientation H with the following property: If an edge uv belongs to a cycle of length k in G, then uv or vu belongs to a directed cycle of length at most h(k) in H. Next, we show that every undirected bridgeless graph of radius r admits an orientation of radius at most r2 + r, and this bound is best possible. We consider the same problem with radius replaced by diameter. Finilly, we show that the problem of deciding whether an undirected graph admits an orientation of diameter (resp. radius) 2 belongs to a class of problems called NP-hard. 相似文献
7.
V. Chvátal 《Discrete Mathematics》1973,5(3):215-228
The toughness of a graph G is defined as the largest real number t such that deletion of any s points from G results in a graph which is either connected or else has at most s/t components. Clearly, every hamiltonian graph is 1-tough. Conversely, we conjecture that for some t0, every t0-tough graph is hamiltonian. Since a square of a k-connected graph is always k-tough, a proof of this conjecture with t0 = 2 would imply Fleischner's theorem (the square of a block is hamiltonian). We construct an infinite family of ()-tough nonhamiltonian graphs. 相似文献
8.
Václav Chvátal 《Mathematical Programming》1973,5(1):29-40
Jack Edmonds developed a new way of looking at extremal combinatorial problems and applied his technique with a great success to the problems of the maximal-weight degreeconstrained subgraphs. Professor C. St. J.A. Nash-Williams suggested to use Edmonds' approach in the context of hamiltonian graphs. In the present paper, we determine a new set of inequalities (the comb inequalities) which are satisfied by the characteristic functions of hamiltonian circuits but are not explicit in the straightforward integer programming formulation. A direct application of the linear programming duality theorem then leads to a new necessary condition for the existence of hamiltonian circuits; this condition appears to be stronger than the ones previously known. Relating linear programming to hamiltonian circuits, the present paper can also be seen as a continuation of the work of Dantzig, Fulkerson and Johnson on the traveling salesman problem. 相似文献
9.
V. Chvátal 《Discrete Mathematics》1979,25(3):285-287
10.
For each positive integerk, we consider the setA
k
of all ordered pairs [a, b] such that in everyk-graph withn vertices andm edges some set of at mostam+bn vertices meets all the edges. We show that eachA
k
withk2 has infinitely many extreme points and conjecture that, for every positive , it has only finitely many extreme points [a, b] witha. With the extreme points ordered by the first coordinate, we identify the last two extreme points of everyA
k
, identify the last three extreme points ofA
3, and describeA
2 completely. A by-product of our arguments is a new algorithmic proof of Turán's theorem. 相似文献