Realizability of Score sequence pair of an (r11, r12, r22)-tournament

Masaya Takahashi; Takahiro Watanabe; Takeshi Yoshimura

doi:10.1109/APCCAS.2006.342261

Realizability of Score sequence pair of an (r₁₁, r₁₂, r₂₂)-tournament

Masaya Takahashi^*, Takahiro Watanabe, Takeshi Yoshimura

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Let G be any directed graph and S be nonnegative and non-decreasing integer sequence(s). The prescribed degree sequence problem is a problem to determine whether there is a graph G with S as the prescribed sequence(s) of outdegrees of the vertices. Let G be the property satisfying the following (1) and (2): (1) G has two disjoint vertex sets A and B. (2) For every vertex pair u, v∈ G (u ≠ v), G satisfies |{HV}| + |{VH}|= {r₁₁ if u, v∈ A {r ₁₂ if u∈ A, v∈ B {r₂₂ if u, v ∈ B, where uv (vu, respectively) means a directed edges from u to v (from v to u). Then G is called an (r₁₁,r₁₂,r₂₂)-tournament ("tournament", for short). When G is a "tournament," the prescribed degree sequence problem is called the score sequence pair problem of a "tournament", and S is called a score sequence pair of a "tournament" (or S is realizable) if the answer is "yes." In this paper, we propose the characterizations of a "tournament" and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not.

Original language	English
Title of host publication	APCCAS 2006 - 2006 IEEE Asia Pacific Conference on Circuits and Systems
Pages	1019-1022
Number of pages	4
DOIs	https://doi.org/10.1109/APCCAS.2006.342261
Publication status	Published - 2006
Externally published	Yes
Event	APCCAS 2006 - 2006 IEEE Asia Pacific Conference on Circuits and Systems - , Singapore Duration: 2006 Dec 4 → 2006 Dec 6

Publication series

Name	IEEE Asia-Pacific Conference on Circuits and Systems, Proceedings, APCCAS

Conference

Conference	APCCAS 2006 - 2006 IEEE Asia Pacific Conference on Circuits and Systems
Country/Territory	Singapore
Period	06/12/4 → 06/12/6

Keywords

Algorithm
Graph theory
Prescribed degrees
Realizable
Score sequence
Tournament

ASJC Scopus subject areas

Electrical and Electronic Engineering

Access to Document

10.1109/APCCAS.2006.342261

Cite this

Realizability of Score sequence pair of an (r₁₁, r₁₂, r₂₂)-tournament. / Takahashi, Masaya; Watanabe, Takahiro; Yoshimura, Takeshi.
APCCAS 2006 - 2006 IEEE Asia Pacific Conference on Circuits and Systems. 2006. p. 1019-1022 4145569 (IEEE Asia-Pacific Conference on Circuits and Systems, Proceedings, APCCAS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Takahashi, M, Watanabe, T & Yoshimura, T 2006, Realizability of Score sequence pair of an (r₁₁, r₁₂, r₂₂)-tournament. in APCCAS 2006 - 2006 IEEE Asia Pacific Conference on Circuits and Systems., 4145569, IEEE Asia-Pacific Conference on Circuits and Systems, Proceedings, APCCAS, pp. 1019-1022, APCCAS 2006 - 2006 IEEE Asia Pacific Conference on Circuits and Systems, Singapore, 06/12/4. https://doi.org/10.1109/APCCAS.2006.342261

@inproceedings{10c5da945d264980a691155a8fbe4339,

title = "Realizability of Score sequence pair of an (r11, r12, r22)-tournament",

abstract = "Let G be any directed graph and S be nonnegative and non-decreasing integer sequence(s). The prescribed degree sequence problem is a problem to determine whether there is a graph G with S as the prescribed sequence(s) of outdegrees of the vertices. Let G be the property satisfying the following (1) and (2): (1) G has two disjoint vertex sets A and B. (2) For every vertex pair u, v∈ G (u ≠ v), G satisfies |{HV}| + |{VH}|= {r11 if u, v∈ A {r 12 if u∈ A, v∈ B {r22 if u, v ∈ B, where uv (vu, respectively) means a directed edges from u to v (from v to u). Then G is called an (r11,r12,r22)-tournament ({"}tournament{"}, for short). When G is a {"}tournament,{"} the prescribed degree sequence problem is called the score sequence pair problem of a {"}tournament{"}, and S is called a score sequence pair of a {"}tournament{"} (or S is realizable) if the answer is {"}yes.{"} In this paper, we propose the characterizations of a {"}tournament{"} and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not.",

keywords = "Algorithm, Graph theory, Prescribed degrees, Realizable, Score sequence, Tournament",

author = "Masaya Takahashi and Takahiro Watanabe and Takeshi Yoshimura",

year = "2006",

doi = "10.1109/APCCAS.2006.342261",

language = "English",

isbn = "1424403871",

series = "IEEE Asia-Pacific Conference on Circuits and Systems, Proceedings, APCCAS",

pages = "1019--1022",

booktitle = "APCCAS 2006 - 2006 IEEE Asia Pacific Conference on Circuits and Systems",

note = "APCCAS 2006 - 2006 IEEE Asia Pacific Conference on Circuits and Systems ; Conference date: 04-12-2006 Through 06-12-2006",

}

TY - GEN

T1 - Realizability of Score sequence pair of an (r11, r12, r22)-tournament

AU - Takahashi, Masaya

AU - Watanabe, Takahiro

AU - Yoshimura, Takeshi

PY - 2006

Y1 - 2006

N2 - Let G be any directed graph and S be nonnegative and non-decreasing integer sequence(s). The prescribed degree sequence problem is a problem to determine whether there is a graph G with S as the prescribed sequence(s) of outdegrees of the vertices. Let G be the property satisfying the following (1) and (2): (1) G has two disjoint vertex sets A and B. (2) For every vertex pair u, v∈ G (u ≠ v), G satisfies |{HV}| + |{VH}|= {r11 if u, v∈ A {r 12 if u∈ A, v∈ B {r22 if u, v ∈ B, where uv (vu, respectively) means a directed edges from u to v (from v to u). Then G is called an (r11,r12,r22)-tournament ("tournament", for short). When G is a "tournament," the prescribed degree sequence problem is called the score sequence pair problem of a "tournament", and S is called a score sequence pair of a "tournament" (or S is realizable) if the answer is "yes." In this paper, we propose the characterizations of a "tournament" and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not.

AB - Let G be any directed graph and S be nonnegative and non-decreasing integer sequence(s). The prescribed degree sequence problem is a problem to determine whether there is a graph G with S as the prescribed sequence(s) of outdegrees of the vertices. Let G be the property satisfying the following (1) and (2): (1) G has two disjoint vertex sets A and B. (2) For every vertex pair u, v∈ G (u ≠ v), G satisfies |{HV}| + |{VH}|= {r11 if u, v∈ A {r 12 if u∈ A, v∈ B {r22 if u, v ∈ B, where uv (vu, respectively) means a directed edges from u to v (from v to u). Then G is called an (r11,r12,r22)-tournament ("tournament", for short). When G is a "tournament," the prescribed degree sequence problem is called the score sequence pair problem of a "tournament", and S is called a score sequence pair of a "tournament" (or S is realizable) if the answer is "yes." In this paper, we propose the characterizations of a "tournament" and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not.

KW - Algorithm

KW - Graph theory

KW - Prescribed degrees

KW - Realizable

KW - Score sequence

KW - Tournament

UR - http://www.scopus.com/inward/record.url?scp=50249089565&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=50249089565&partnerID=8YFLogxK

U2 - 10.1109/APCCAS.2006.342261

DO - 10.1109/APCCAS.2006.342261

M3 - Conference contribution

AN - SCOPUS:50249089565

SN - 1424403871

SN - 9781424403875

T3 - IEEE Asia-Pacific Conference on Circuits and Systems, Proceedings, APCCAS

SP - 1019

EP - 1022

BT - APCCAS 2006 - 2006 IEEE Asia Pacific Conference on Circuits and Systems

T2 - APCCAS 2006 - 2006 IEEE Asia Pacific Conference on Circuits and Systems

Y2 - 4 December 2006 through 6 December 2006

ER -