On a geometric property of perfect graphs

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.     

Authentication schemes from actions on graphs, groups, or rings

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.     

Group testing for consecutive positives

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.     

The struction of a graph: Application toCN-free graphs

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.     

Paired domination on interval and circular-arc graphs

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.     

Chordal bipartite graphs and crowns

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.     

Triples,current graphs and biembeddings

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.     

Explicit constructions of graphs without short cycles and low density codes

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.     

A remark on covering graphs

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.     

Growing perfect cubes

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 c_j×c_j×c_j sized prefix is an (n_j,a,c_j)-perfect double cube for , where and n₁<n₂<?. We construct the smallest possible perfect double cube (a 256×256×256 sized 8-ary array) and growing cubes for any a.     

On k -diameter of k -connected graphs

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).     

Posets with interval upper bound graphs

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.     

Distance distributions for graphs modeling computer networks

The Wiener polynomial of a graph G is a generating function for the distance distribution dd(G)=(D₁,D₂,…,D_t), where D_i 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.     

Legal coloring of graphs

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.     

H-extension of graphs

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.     

Fully-Dynamic Min-Cut*

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(n^2/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.     

Perfect couples of graphs

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.     

On pallets for Fox colorings of spatial graphs

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.     

Solution to a problem of C. D. Godsil regarding bipartite graphs with unique perfect matching

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.     

On 3-pushdown graphs with large separators

For an integers letl ^s (n), thes-iterated logarithm function, be defined inductively:l ⁰ (n)=n,l ^s+1 (n)=log₂ (l ² (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.