Journal: Discrete Applied Mathematics

Found 533 papers in total
Cyclic graphs
Cyclic graphs
2000,
A subclass of the class of circulant graphs is considered. It is shown that in this...
On the strong chromatic index of cyclic multigraphs
On the strong chromatic index of cyclic multigraphs
2000,
We study the strong chromatic index of multigraphs whose underlying graph is a cycle....
Independent sets with domination constraints
Independent sets with domination constraints
2000,
A ρ-independent set S in a graph is parameterized by a set ρ of non-negative...
Reducible configurations for the cycle double cover conjecture
Reducible configurations for the cycle double cover conjecture
2000,
A CDC (cycle double cover) of a graph G is a system ( C 1 ,...,C k ) of cycles in G...
Connected domination and dominating clique in trapezoid graphs
Connected domination and dominating clique in trapezoid graphs
2000,
The class of trapezoid graphs is a subclass of cocomparability graphs and contains...
Domination and total domination on asteroidal triple-free graphs
Domination and total domination on asteroidal triple-free graphs
2000,
We present the first polynomial time algorithms for solving the NP-complete graph...
Covering a rectangle with six and seven circles
Covering a rectangle with six and seven circles
2000,
In a recent article Heppes and Melissen have determined the thinnest coverings of a...
N-extendible posets, and how to minimize total weighted completion time
N-extendible posets, and how to minimize total weighted completion time
2000,
P 4 -extendible graphs have been introduced by Jamison and Olariu as one of several...
Recognizing k-path graphs
Recognizing k-path graphs
2000,
The k -path graph P k ( H ) of a graph H has all length- k paths of H as vertices; two...
Uncolorable mixed hypergraphs
Uncolorable mixed hypergraphs
2000,
A mixed hypergraph H = ( X ,A,E ) consists of the vertex set X and two families of...
Pancyclic out-arcs of a vertex in tournaments
Pancyclic out-arcs of a vertex in tournaments
2000,
Thomassen proved that every strong tournament contains a vertex x such that each arc...
Subtrees of bipartite digraphs the minimum degree condition
Subtrees of bipartite digraphs the minimum degree condition
2000,
Let D be a bipartite digraph and let T be an oriented tree of order k . We consider...
How to survive while visiting a graph
How to survive while visiting a graph
2000,
A visit of a graph is a permutation of its vertices which establishes the order in...
Recognition and isomorphism of tree-like P4-connected graphs
Recognition and isomorphism of tree-like P4-connected graphs
2000,
A graph is P 4 -connected if, for every partition of its vertices into two nonempty...
Not every 2-tough graph is Hamiltonian
Not every 2-tough graph is Hamiltonian
2000,
We present (9/4–•)-tough graphs without a Hamilton path for arbitrary...
Chordality and 2-factors in tough graphs
Chordality and 2-factors in tough graphs
2000,
A graph G is chordal if it contains no chordless cycle of length at least four and is...
Recognizing the P4-structure of block graphs
Recognizing the P4-structure of block graphs
2000,
A 4-uniform hypergraph represents the P 4 -structure of a graph G , if its hyperedges...
A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
2000,
A graph is distance hereditary if it preserves distances in all its connected induced...
Strongly orderable graphs: A common generalization of strongly chordal and chordal bipartite graphs
Strongly orderable graphs: A common generalization of strongly chordal and chordal bipartite graphs
2000,
In this paper those graphs are studied for which a so-called strong ordering of the...
On the classification of NP-complete problems in terms of their correlation coefficient
On the classification of NP-complete problems in terms of their correlation coefficient
2000,
Local search and its variants simulated annealing and tabu search are very popular...
On complexity, representation and approximation of integral multicommodity flows
On complexity, representation and approximation of integral multicommodity flows
2000,
The paper has two parts. In the algorithmic part integer inequality systems of packing...
The maximum travelling salesman problem on symmetric Demidenko matrices
The maximum travelling salesman problem on symmetric Demidenko matrices
2000,
It is well-known that the Travelling Salesman Problem (TSP) is solvable in polynomial...
Tree partitioning under constraints – clustering for vehicle routing problems
Tree partitioning under constraints – clustering for vehicle routing problems
2000,
We present a dynamic programming algorithm for the following problem: Given a tree T =...
Some extremal properties of the degree distance of a graph
Some extremal properties of the degree distance of a graph
1999,
This paper deals with two conjectures made by Dobrynin and Kochetova on the minimum...
Papers per page: