Focality and graph isomorphism

Wilfried Imrich; G. Sabidussi

doi:10.1016/0012-365X(90)90063-N

Focality and graph isomorphism

Wilfried Imrich
, G. Sabidussi

Lehrstuhl für Angewandte Mathematik (170)

University of Montreal

Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › Begutachtung

Abstract

A graph is focal if the stabiliser of every vertex x fixes exactly one edge not incident with x. It is shown that the problem of testing whether a connected bipartite grpah is focal has the same complexity as the graph isomorphism problem. Several other similar questions are also considered.

Originalsprache	Englisch
Seiten (von - bis)	237-245
Seitenumfang	9
Fachzeitschrift	Discrete mathematics
Jahrgang	81.1990
Ausgabenummer	3
DOIs	https://doi.org/10.1016/0012-365X(90)90063-N
Publikationsstatus	Veröffentlicht - 1 Mai 1990

Zugriff auf Dokument

10.1016/0012-365X(90)90063-N

Andere Dateien und Links

Link to publication in Scopus

Dieses zitieren

@article{eb877393feba4b6aab8ad1971b5a9c8d,

title = "Focality and graph isomorphism",

abstract = "A graph is focal if the stabiliser of every vertex x fixes exactly one edge not incident with x. It is shown that the problem of testing whether a connected bipartite grpah is focal has the same complexity as the graph isomorphism problem. Several other similar questions are also considered.",

author = "Wilfried Imrich and G. Sabidussi",

year = "1990",

month = may,

day = "1",

doi = "10.1016/0012-365X(90)90063-N",

language = "English",

volume = "81.1990",

pages = "237--245",

journal = "Discrete mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Focality and graph isomorphism

AU - Imrich, Wilfried

AU - Sabidussi, G.

PY - 1990/5/1

Y1 - 1990/5/1

N2 - A graph is focal if the stabiliser of every vertex x fixes exactly one edge not incident with x. It is shown that the problem of testing whether a connected bipartite grpah is focal has the same complexity as the graph isomorphism problem. Several other similar questions are also considered.

AB - A graph is focal if the stabiliser of every vertex x fixes exactly one edge not incident with x. It is shown that the problem of testing whether a connected bipartite grpah is focal has the same complexity as the graph isomorphism problem. Several other similar questions are also considered.

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

U2 - 10.1016/0012-365X(90)90063-N

DO - 10.1016/0012-365X(90)90063-N

M3 - Article

AN - SCOPUS:44949287169

SN - 0012-365X

VL - 81.1990

SP - 237

EP - 245

JO - Discrete mathematics

JF - Discrete mathematics

IS - 3

ER -