Discrete Applied Mathematics

Items from 1 to 20 out of 35 results

article

On the PBD-closure of sets containing 3

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 251-272

We describe a method used to prove nonexistence of pairwise balanced designs and determine the exact closure of all subsets K of the set {3,4,...,22} with K {11,12,...,22}<> and 3 K.

article

Tree- and forest-perfect graphs

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 141-162

Two graphs G and H with the same vertex set V are P ₄ -isomorphic if there exists a permutation π on V such that, for all subsets S V,S induces a chordless path on four vertices (denoted by P ₄ ) in G if and only if π(S) induces a P ₄ in H. This paper gives a classification of all graphs P ₄ -isomorphic to a tree, respectively, a forest.

article

Almost diameter of a house-hole-free graph in linear time via LexBFS

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 223-239

We show that the vertex visited last by a LexBFS has eccentricity at least diam(G)-2 for house-hole-free graphs, at least diam(G)-1 for house-hole-domino-free graphs, and equal to diam(G) for house-hole-domino-free and AT-free graphs. To prove these results we use special metric properties of house-hole-free graphs with respect to LexBFS.

article

On maximal shadows of members in left-compressed sets

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 3-9

Whereas Stanley, Proctor and others studied Sperner properties of the poset L(k,m) we consider shadows of left-compressed sets and derive asymptotic bounds on their sizes.

article

On the stability number of claw-free P ₅ -free and more general graphs

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 163-167

In this note we show that the stability number of a (4-pan, chair, K ₁ _, ₄ ,P ₅ )-free graph which has no simplicial vertex is bounded by 3. This generalizes the case of (claw, P ₅ )-free graphs and leads to a very simple polynomial-time algorithm for determining the stability number of (claw, P ₅ )-free graphs and, more generally, of (4-pan,chair, K ₁ ...

article

Covering t-sets with (t+2)-sets

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 425-437

New upper bounds for C(v,k,t), the minimum number of k-subsets (blocks) out of a v-set such that each t-subset is contained in at least one block, are obtained by constructing corresponding covering designs with prescribed automorphisms. Computer search with a stochastic heuristic, tabu search, is used to find the covering designs. The new covering designs are listed and a table of upper bounds on...

article

The Steiner ratio of L ₂ _k ^d

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 217-221

Let L ₂ _k ^d be the d-dimensional space with 2k-norm. Given a finite set N of points in this space. Find a connected graph G=(V,E) such that N V and the total length of G is minimal. Such a network is called a Steiner minimal tree (SMT). If we connect pairs of given points only, we find a minimum spanning tree (MST). Whereas an MST is easy to find a method to construct an SMT in L...

article

The Erdos-Ko-Rado bound for the function lattice

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 115-125

We answer the following question: When does a k-uniform family generated by some rank t element in the function lattice have maximum size among all k-uniform t-intersecting families?

article

Perfect and almost perfect sequences

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 331-359

The autocorrelation function of a sequence is a measure for how much the given sequence differs from its translates. Periodic binary sequences with good correlation properties have important applications in various areas of engineering. In particular, one needs sequences with a two-level autocorrelation function, that is, all nontrivial autocorrelation coefficients equal some constant γ. The case...

article

Outpaths in semicomplete multipartite digraphs

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 273-277

An outpath of a vertex x (an arc xy, respectively) in a digraph is a directed path starting at x (xy, respectively) such that x dominates the endvertex of the path only if the endvertex also dominates x. Firstly, we show that if D is a strongly connected semicomplete n-partite (n>=3) digraph, then every vertex v of D has an outpath of length k-1 for all k {3,4,...,n}. Our result generalizes a...

article

Recognizing graphs of acyclic cubical complexes

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 321-330

Acyclic cubical complexes have first been introduced by Bandelt and Chepoi in analogy to acyclic simplicial complexes. They characterized them by cube contraction and elimination schemes and showed that the graphs of acyclic cubical complexes are retracts of cubes characterized by certain forbidden convex subgraphs. In this paper we present an algorithm of time complexity O(mlogn) which recognizes...

article

A brief survey of perfect Mendelsohn packing and covering designs

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 73-81

A (v,k,λ)-perfect Mendelsohn packing (covering) design is a pair (X,A) where X is a v-set of points and A is a collection of cyclically ordered k-subsets of X, called blocks, such that every ordered pair of points of X appears t-apart in at most (at least) λ blocks of A for all t=1,2,...,k-1. If no other such packing (covering) has more (fewer) blocks, the packing (covering) is said to be maximum...

article

On the complexity of hamiltonian path and cycle problems in certain classes of digraphs

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 41-60

We survey results on the sequential and parallel complexity of hamiltonian path and cycle problems in various classes of digraphs which generalize tournaments. We give detailed informations on the difference in difficulties for these problems for the various classes as well as prove new results on hamiltonian paths starting in a specified vertex for a quite general class of digraphs.

article

Graph classes between parity and distance-hereditary graphs

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 197-216

Several graph problems (e.g., steiner tree, connected domination, hamiltonian path, and isomorphism problem), which can be solved in polynomial time for distance-hereditary graphs, are NP-complete or open for parity graphs. Moreover, the metric characterizations of these two graph classes suggest an excessive gap between them. We introduce a family of classes forming an infinite lattice with respect...

article

Matching-star Ramsey sets

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 417-424

The Ramsey set R(G,H) consists of all graphs F with F->(G,H) and F' (G,H) for every proper subgraph F' of F. In this paper we will characterize the graphs belonging to R(2K ₂ ,K ₁ _, _n ) with n>=3 and determine R(2K ₂ ,K ₁ _, _n ) for n=<3 explicitly.

article

An upper bound for the size of the largest antichain in the poset of partitions of an integer

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 169-180

Let Pi _n be the poset of partitions of an integer n, ordered by refinement. Let b(Pi _n ) be the largest size of a level and d(Pi _n ) be the largest size of an antichain of Pi _n . We prove thatd(Pi _n )b(Pi _n )=<e+o(1)asn->~.The denominator is determined asymptotically. In addition, we show that the incidence matrices in the lower half of Pi ...

article

On the extension of bipartite to parity graphs

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 181-195

Parity graphs form a superclass of bipartite and distance-hereditary graphs. Since their introduction, all the algorithms proposed as solutions to the recognition problem and other combinatorial problems exploit the structural property of these graphs described by Burlet and Uhry (Berge and Chvatal (Eds.), Topics on Perfect Graphs, Ann. Discrete Math., vol. 21, North-Holland, Amsterdam, 1984, pp....

article

Index

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 467-468

article

On the linear relaxation of the 2-node connected subgraph polytope

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 389-416

In this paper, we study the linear relaxation P(G) of the 2-node connected subgraph polytope of a graph G. We introduce an ordering on the fractional extreme points of P(G) and we give a characterization of the minimal extreme points with respect to that ordering. This yields a polynomial method to separate a minimal extreme point of P(G) from the 2-node connected subgraph polytope. It also provides...

article

On k-partitioning of Hamming graphs

Discrete Applied Mathematics > 1999 > 95 > 1-3 > 127-140

We consider the graphs H _a ⁿ defined as the Cartesian products of n complete graphs with a vertices each. Let an edge cut partition the vertex set of a graph into k subsets A ₁ ,...,A _k with ||A _i |-|A _j ||=<1. We consider the problem of determining the minimal size of such a cut for the graphs defined above and present bounds and asymptotic results for...

Number:
1-3
Volume:
95
Year:
1999

Publication date

Set your own date range

Keywords

COMPLEXITY (2)
EDGE PARTITION (2)
HAMILTONIAN CYCLE (2)
HAMILTONIAN PATH (2)
IN-SEMICOMPLETE DIGRAPH (2)
PARITY GRAPHS (2)
PERFECT GRAPHS (2)
RECOGNITION PROBLEM (2)
SEMICOMPLETE MULTIPARTITE DIGRAPH (2)
GRAPHS WITH P 4 -STRUCTURE OF TREES (1)
P 4 -STRUCTURE OF PERFECT GRAPHS (1)
2-NODE CONNECTED GRAPH (1)
ACYCLIC CUBICAL COMPLEX (1)
ALGORITHM (1)
ALMOST PERFECT SEQUENCE (1)
AT-FREE GRAPHS (1)
AUTOCORRELATION FUNCTION (1)
AUTOMORPHISM GROUP (1)
BALANCED INCOMPLETE BLOCK DESIGNS (1)
BARKER SEQUENCE (1)
BINARY ENTROPY (1)
BINARY SEQUENCE (1)
BSS-MODEL (1)
CHARACTERIZATION (1)
CLAW-FREE GRAPHS (1)
COMBINATORIAL OPTIMIZATION (1)
COMPLETE DIGRAPH (1)
COMPLETE DIRECTED MULTIGRAPH (1)
CONSTRUCTIVE COMBINATORICS (1)
COVERING DESIGN (1)
CRITICAL EDGES (1)
CRITICAL EXTREME POINT (1)
CUNNINGHAM DECOMPOSITION (1)
CUT (1)
CYCLE (1)
CYCLE FACTOR (1)
DECOMPOSABLE DIGRAPH (1)
DEGREE CONDITION (1)
DESIGN (1)
DIAMETER (1)
DIFFERENCE SET (1)
DISTANCE-HEREDITARY GRAPHS (1)
ECCENTRICITY (1)
EDGE-ISOPERIMETRIC PROBLEM (1)
ERDOS-KO-RADO BOUND (1)
FINITE RAMSEY SETS (1)
FLOWS (1)
FUNCTION LATTICE (1)
GRAPH DECOMPOSITIONS (1)
GRAPH PARTITIONING (1)
GROUP ACTIONS (1)
HAMILTONIAN CONNECTED (1)
HAMILTONIAN DIGRAPH (1)
HAMMING GRAPHS (1)
HOLEY PERFECT MENDELSOHN DESIGNS (1)
HOUSE-HOLE-DOMINO FREE GRAPHS (1)
HOUSE-HOLE-FREE GRAPHS (1)
HYPERCUBES (1)
INCOMPLETE PERFECT MENDELSOHN DESIGNS (1)
INDEPENDENCE NUMBER (1)
INTERSECTING FAMILY (1)
ISOMORPHISM PROBLEM (1)
LEFT-PUSHING ORDER (1)
LEXBFS (1)
LINE GRAPHS (1)
LINEAR SPACE (1)
LINEAR TIME RECOGNITION (1)
LINEAR-TIME ALGORITHM (1)
LINKAGE (1)
LOCALLY SEMICOMPLETE DIGRAPH (1)
LOCALLY SEMICOMPLETE DIGRAPHS (1)
LONGEST PATH (1)
MAXIMAL ELEMENTS (1)
MAXIMUM WEIGHTED CLIQUE PROBLEM (1)
MAXIMUM WEIGHTED INDEPENDENT SET PROBLEM (1)
MEDIAN GRAPH (1)
MERIT FACTOR (1)
MEYNIELS THEOREM (1)
MULTIPARTITE TOURNAMENT (1)
NETWORK RELIABILITY (1)
ODC (1)
ORTHOGONAL DOUBLE COVER (1)
PACKING AND COVERING DESIGNS (1)
PAIRWISE BALANCED DESIGN (1)
PARALLEL ALGORITHM (1)
PARAMETERS OF GEOMETRIES (1)
PATH (1)
PATH COVERING (1)
PATH FACTOR (1)
PATH-MERGEABLE DIGRAPH (1)
PATHWIDTH (1)
PBD-CLOSURE (1)
PERFECT MENDELSOHN DESIGNS (1)
PERFECT SEQUENCE (1)
PERIODIC SEQUENCE (1)
POLYNOMIAL ALGORITHM (1)
POLYNOMIAL-TIME ALGORITHM (1)
POLYTOPE (1)
PRODUCT OF COMPLETE GRAPHS (1)
PROPER LINEAR SPACE (1)
more

INFONA - science communication portal

Discrete Applied Mathematics

On the PBD-closure of sets containing 3

Tree- and forest-perfect graphs

Almost diameter of a house-hole-free graph in linear time via LexBFS

On maximal shadows of members in left-compressed sets

On the stability number of claw-free P ₅ -free and more general graphs

Covering t-sets with (t+2)-sets

The Steiner ratio of L ₂ _k ^d

The Erdos-Ko-Rado bound for the function lattice

Perfect and almost perfect sequences

Outpaths in semicomplete multipartite digraphs

Recognizing graphs of acyclic cubical complexes

A brief survey of perfect Mendelsohn packing and covering designs

On the complexity of hamiltonian path and cycle problems in certain classes of digraphs

Graph classes between parity and distance-hereditary graphs

Matching-star Ramsey sets

An upper bound for the size of the largest antichain in the poset of partitions of an integer

On the extension of bipartite to parity graphs

Index

On the linear relaxation of the 2-node connected subgraph polytope

On k-partitioning of Hamming graphs

Filter options

Publication date

Keywords

INFONA - science communication portal

Discrete Applied Mathematics

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Keywords

Reporting an error / abuse

Sending the report failed

Accessibility options