共查询到20条相似文献,搜索用时 10 毫秒
1.
LetG be a graph,VP(G) its vertex packing polytope and letA(G) be obtained by reflectingVP(G) in all Cartersian coordinates. Denoting byA*(G) the set obtained similarly from the fractional vertex packing polytope, we prove that the segment connecting any two non-antipodal
vertices ofA(G) is contained in the surface ofA(G) and thatG is perfect if and only ifA*(G) has a similar property. 相似文献
2.
We propose a couple of general ways of constructing authentication schemes from actions of a semigroup on a set, without exploiting any specific algebraic properties of the set acted upon. Then we give several concrete realizations of this general idea, and in particular, we describe several authentication schemes with long-term private keys where forgery (a.k.a. impersonation) is NP-hard. Computationally hard problems that can be employed in these realizations include the Graph Colorability problem, the Diophantine problem, and many others. 相似文献
3.
Charles J. Colbourn 《Annals of Combinatorics》1999,3(1):37-41
Strategies for adaptive and nonadaptive group testing are developed when the items are linearly ordered and the positive items form a consecutive subset of all items.The research was supported in part by the US Army Research Office under Grant DAAG55-98-1-0272. 相似文献
4.
We consider the class of graphs characterized by the forbidden subgraphsC andN:C is the claw (unique graph with degree sequence (3, 1, 1, 1)) andN the net (unique graph with degree sequence (3, 3, 3, 1, 1, 1)). For this class of graphs (calledCN-free) an algorithm is described for determining the stability numberα(G). It is based on a construction associating with anyCN-free graphG anotherCN-free graphG′ such thatα(G′)=α(G)−1. Such a construction reducing the stability number is called a struction.
This work was completed while this author was visiting the Dept. of Combinatories and Optimization at the University of Waterloo,
Ontario. 相似文献
5.
Paired domination on interval and circular-arc graphs 总被引:1,自引:0,他引:1
We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O(m+n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O(m(m+n)) time. 相似文献
6.
Vincent Bouchitté 《Order》1985,2(2):119-122
We prove that a bipartite graph is chordal if and only if it has an elimination scheme. This leads to a polynomial algorithm to recognize whether an ordered set is cycle-free. 相似文献
7.
Ian Anderson 《Aequationes Mathematicae》1982,24(1):230-242
A family of ladder graphs, used by Youngs in his work on the Heawood conjecture, is used to provide constructions of Skolem and related triple systems, triangular biembeddings of certain complete graphs, and genus embeddings of certain complete multipartite graphs. 相似文献
8.
G. A. Margulis 《Combinatorica》1982,2(1):71-78
We give an explicit construction of regular graphs of degree 2r withn vertices and girth ≧c logn/logr. We use Cayley graphs of factor groups of free subgroups of the modular group. An application to low density codes is given. 相似文献
9.
Pavel Holub 《Order》1985,2(3):321-322
Every graph G may be transformed into a covering graph either by deletion of edges or by subdivision. Let
E
(G) and
V
(G) denote corresponding minimal numbers. We prove
E
(G) =
V
(G) for every graph G. 相似文献
10.
Márk Horváth 《Discrete Mathematics》2008,308(19):4378-4388
An (n,a,b)-perfect double cube is a b×b×b sized n-ary periodic array containing all possible a×a×a sized n-ary array exactly once as subarray. A growing cube is an array whose cj×cj×cj sized prefix is an (nj,a,cj)-perfect double cube for , where and n1<n2<?. We construct the smallest possible perfect double cube (a 256×256×256 sized 8-ary array) and growing cubes for any a. 相似文献
11.
Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer d
k
(G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most d
k
(G). For a fixed positive integer d, some conditions to insure d
k
(G)⩽d are given in this paper. In particular, if d⩾3 and the sum of degrees of any s (s=2 or 3) nonadjacent vertices is at least n+(s−1)k+1−d, then d
k
(G)⩽d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible.
Supported by NNSF of China (19971086). 相似文献
12.
Debra D. Scott 《Order》1986,3(3):269-281
Competition graphs of transitive acyclic digraphs are strict upper bound graphs. This paper characterizes those posets, which can be considered transitive acyclic digraphs, which have upper bound graphs that are interval graphs. The results proved here may shed some light on the open question of those digraphs which have interval competition graphs.This material is taken from Chapter 3 of my (maiden name Diny) PhD Dissertation. 相似文献
13.
Bruce Elenbogen 《Discrete Applied Mathematics》2007,155(18):2612-2624
The Wiener polynomial of a graph G is a generating function for the distance distribution dd(G)=(D1,D2,…,Dt), where Di is the number of unordered pairs of distinct vertices at distance i from one another and t is the diameter of G. We use the Wiener polynomial and several related generating functions to obtain generating functions for distance distributions of unweighted and weighted graphs that model certain large classes of computer networks. These provide a straightforward means of computing distance and timing statistics when designing new networks or enlarging existing networks. 相似文献
14.
N. Linial 《Combinatorica》1986,6(1):49-54
The following computational problem was initiated by Manber and Tompa (22nd FOCS Conference, 1981): Given a graphG=(V, E) and a real functionf:V→R which is a proposed vertex coloring. Decide whetherf is a proper vertex coloring ofG. The elementary steps are taken to be linear comparisons.
Lower bounds on the complexity of this problem are derived using the chromatic polynomial ofG. It is shown how geometric parameters of a space partition associated withG influence the complexity of this problem.
Existing methods for analyzing such space partitions are suggested as a powerful tool for establishing lower bounds for a
variety of computational problems. 相似文献
15.
We consider the problem of constructing a graphG* from a collection of isomorphic copies of a graphG in such a way that for every two copies ofG, either no vertices or a section graph isomorphic to a graphH is identified. It is shown that ifG can be partitioned into vertex-disjoint copies ofH, thenG* can be made to have at most |H| orbits. A condition onG so thatG* can be vertextransitive is also included. 相似文献
16.
Mikkel Thorup 《Combinatorica》2007,27(1):91-127
We show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in
worst-case time per edge insertion or deletion. Within logarithmic factors, this matches the best time bound for 1-edge connectivity.
Previously, no o(n) bound was known for edge connectivity above 3, and even for 3-edge connectivity, the best update time was O(n2/3), dating back to FOCS'92.
Our algorithm maintains a concrete min-cut in terms of a pointer to a tree spanning one side of the cut plus ability to list
the cut edges in O(log n) time per edge.
By dealing with polylogarithmic edge connectivity, we immediately get a sampling based expected factor (1+o(1)) approximation to general edge connectivity in
time per edge insertion or deletion. This algorithm also maintains a pointer to one side of a near-minimal cut, but if we
want to list the cut edges in O(log n) time per edge, the update time increases to
.
* A preliminary version of this work was presented at the The 33rd ACM Symposium on Theory of Computing( STOC) [22], Crete, Greece, July 2001. 相似文献
17.
We generalize the concept of perfect graphs in terms of additivity of a functional called graph entropy. The latter is an information theoretic functional on a graphG with a probability distributionP on its vertex set. For any fixedP it is sub-additive with respect to graph union. The entropy of the complete graph equals the sum of those ofG and its complement G iffG is perfect. We generalize this recent result to characterize all the cases when the sub-additivity of graph entropy holds with equality.The research of the authors is partially supported by the Hungarian National Foundation for Scientific Research (OTKA), grant No. 1806 resp. No. 1812. 相似文献
18.
Kanako Oshiro 《Topology and its Applications》2012,159(4):1092-1105
We introduce the notion of pallets of quandles and define coloring invariants for spatial graphs which give a generalization of Fox colorings studied in Ishii and Yasuhara (1997) [4]. All pallets for dihedral quandles are obtained from the quotient sets of the universal pallets under a certain equivalence relation. We study the quotient sets and classify their elements. 相似文献
19.
We give the solution to the following question of C. D. Godsil[2]: Among the bipartite graphsG with a unique perfect matching and such that a bipartite graph obtains when the edges of the matching are contracted, characterize those having the property thatG
+G, whereG
+ is the bipartite multigraph whose adjacency matrix,B
+, is diagonally similar to the inverse of the adjacency matrix ofG put in lower-triangular form. The characterization is thatG must be obtainable from a bipartite graph by adding, to each vertex, a neighbor of degree one. Our approach relies on the association of a directed graph to each pair (G, M) of a bipartite graphG and a perfect matchingM ofG. 相似文献
20.
For an integers letl
s
(n), thes-iterated logarithm function, be defined inductively:l
0
(n)=n,l
s+1
(n)=log2 (l
2
(n)) fors0. We show that for every fixeds and alln large enough, there is ann-vertex 3-pushdown graph whose smallest separator contains at least(n/l
s
(n)) vertices.The work of the first author was supported in part by NSF Grants MCS-83-03139, DCR-85-11713 and CCR-86-05353.The work of the second author was supported in part by NSF Grants MCS-84-16190. 相似文献