Focality and graph isomorphism

Wilfried Imrich; G. Sabidussi

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

Focality and graph isomorphism

Wilfried Imrich, G. Sabidussi

Chair of Applied Mathematics (170)

University of Montréal, École Polytechnique, Montréal, Canada

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

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.

Original language	English
Pages (from-to)	237-245
Number of pages	9
Journal	Discrete mathematics
Volume	81.1990
Issue number	3
DOIs	https://doi.org/10.1016/0012-365X(90)90063-N
Publication status	Published - 1 May 1990

Access to Document

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

Cite this

@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 - http://www.scopus.com/inward/record.url?scp=44949287169&partnerID=8YFLogxK

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 -

Focality and graph isomorphism

Abstract

Access to Document

Other files and links

Cite this