Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs

Gregory Gutina; Meike Tewes; Anders Yeo

doi:10.1016/s0012-365x(00)00055-8

Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs

Gregory Gutina, Meike Tewes, Anders Yeo

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

Abstract

A digraph obtained by replacing each edge of a complete multipartite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a semicomplete multipartite digraph. Volkmann (Manuscript, RWTH Aachen, Germany, June 1998) raised the following question: Let D be a strong semicomplete multipartite digraph with a longest path of length l. Does there exist a strong spanning oriented subgraph of D with a longest path of length l? We provide examples which show that the answer to this question is negative. We also demonstrate that every strong semicomplete multipartite digraph D, which is not bipartite with a partite set of cardinality one, has a strong spanning oriented subgraph of D with a longest path of length at least l - 2. This bound is sharp.

Original language	English
Pages (from-to)	269-274
Number of pages	6
Journal	Discrete Mathematics
Volume	222
Issue number	1-3
DOIs	https://doi.org/10.1016/s0012-365x(00)00055-8
Publication status	Published - 28 Jul 2000
Externally published	Yes

Keywords

Path
Semicomplete multipartite digraph
Spanning subgraph

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/s0012-365x(00)00055-8

Cite this

@article{52e0056798f848cb9596be9bb2285762,

title = "Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs",

abstract = "A digraph obtained by replacing each edge of a complete multipartite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a semicomplete multipartite digraph. Volkmann (Manuscript, RWTH Aachen, Germany, June 1998) raised the following question: Let D be a strong semicomplete multipartite digraph with a longest path of length l. Does there exist a strong spanning oriented subgraph of D with a longest path of length l? We provide examples which show that the answer to this question is negative. We also demonstrate that every strong semicomplete multipartite digraph D, which is not bipartite with a partite set of cardinality one, has a strong spanning oriented subgraph of D with a longest path of length at least l - 2. This bound is sharp.",

keywords = "Path, Semicomplete multipartite digraph, Spanning subgraph",

author = "Gregory Gutina and Meike Tewes and Anders Yeo",

year = "2000",

month = jul,

day = "28",

doi = "10.1016/s0012-365x(00)00055-8",

language = "English",

volume = "222",

pages = "269--274",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs

AU - Gutina, Gregory

AU - Tewes, Meike

AU - Yeo, Anders

PY - 2000/7/28

Y1 - 2000/7/28

N2 - A digraph obtained by replacing each edge of a complete multipartite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a semicomplete multipartite digraph. Volkmann (Manuscript, RWTH Aachen, Germany, June 1998) raised the following question: Let D be a strong semicomplete multipartite digraph with a longest path of length l. Does there exist a strong spanning oriented subgraph of D with a longest path of length l? We provide examples which show that the answer to this question is negative. We also demonstrate that every strong semicomplete multipartite digraph D, which is not bipartite with a partite set of cardinality one, has a strong spanning oriented subgraph of D with a longest path of length at least l - 2. This bound is sharp.

AB - A digraph obtained by replacing each edge of a complete multipartite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a semicomplete multipartite digraph. Volkmann (Manuscript, RWTH Aachen, Germany, June 1998) raised the following question: Let D be a strong semicomplete multipartite digraph with a longest path of length l. Does there exist a strong spanning oriented subgraph of D with a longest path of length l? We provide examples which show that the answer to this question is negative. We also demonstrate that every strong semicomplete multipartite digraph D, which is not bipartite with a partite set of cardinality one, has a strong spanning oriented subgraph of D with a longest path of length at least l - 2. This bound is sharp.

KW - Path

KW - Semicomplete multipartite digraph

KW - Spanning subgraph

UR - https://www.scopus.com/pages/publications/0013464930

U2 - 10.1016/s0012-365x(00)00055-8

DO - 10.1016/s0012-365x(00)00055-8

M3 - Article

AN - SCOPUS:0013464930

SN - 0012-365X

VL - 222

SP - 269

EP - 274

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this