Primal graphs with small degrees

Phyllis Z. Chinn; R. Bruce Richter; Miroslaw Truszczynski

doi:10.1016/0012-365X(91)90133-M

Primal graphs with small degrees

Phyllis Z. Chinn, R. Bruce Richter, Miroslaw Truszczynski

Computer Science

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

1 Scopus citations

Abstract

It has previously been shown that there is a unique set Π of primal graphs such that every graph has an edge-decomposition into non-isomorphic elements of Π and that the only decomposition of an element of Π into non-isomorphic elements of Π is the obvious one. Here it is shown that there are infinitely many elements of Π even among graphs having a relatively simple structure. On the other hand, within this same class of graphs, we show that 'most' of them are not primal.

Original language	English
Pages (from-to)	237-248
Number of pages	12
Journal	Discrete Mathematics
Volume	87
Issue number	3
DOIs	https://doi.org/10.1016/0012-365X(91)90133-M
State	Published - Feb 22 1991

Bibliographical note

Funding Information:
The second author conducteds ome of this researchw hile at the Ohio State University on a postdoctorals cholarshipf rom the Natural Sciencesa nd Engineering Research Council of Canada. The support of these institutionsi s gratefully acknowledged.

Funding

The second author conducteds ome of this researchw hile at the Ohio State University on a postdoctorals cholarshipf rom the Natural Sciencesa nd Engineering Research Council of Canada. The support of these institutionsi s gratefully acknowledged.

Funders	Funder number
Natural Sciences and Engineering Research Council of Canada
Ohio State University

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(91)90133-M

Cite this

@article{347f7112e7c64b0fa7042b96f43d15ce,

title = "Primal graphs with small degrees",

abstract = "It has previously been shown that there is a unique set Π of primal graphs such that every graph has an edge-decomposition into non-isomorphic elements of Π and that the only decomposition of an element of Π into non-isomorphic elements of Π is the obvious one. Here it is shown that there are infinitely many elements of Π even among graphs having a relatively simple structure. On the other hand, within this same class of graphs, we show that 'most' of them are not primal.",

author = "Chinn, {Phyllis Z.} and Richter, {R. Bruce} and Miroslaw Truszczynski",

note = "Funding Information: The second author conducteds ome of this researchw hile at the Ohio State University on a postdoctorals cholarshipf rom the Natural Sciencesa nd Engineering Research Council of Canada. The support of these institutionsi s gratefully acknowledged.",

year = "1991",

month = feb,

day = "22",

doi = "10.1016/0012-365X(91)90133-M",

language = "English",

volume = "87",

pages = "237--248",

number = "3",

}

TY - JOUR

T1 - Primal graphs with small degrees

AU - Chinn, Phyllis Z.

AU - Richter, R. Bruce

AU - Truszczynski, Miroslaw

N1 - Funding Information: The second author conducteds ome of this researchw hile at the Ohio State University on a postdoctorals cholarshipf rom the Natural Sciencesa nd Engineering Research Council of Canada. The support of these institutionsi s gratefully acknowledged.

PY - 1991/2/22

Y1 - 1991/2/22

N2 - It has previously been shown that there is a unique set Π of primal graphs such that every graph has an edge-decomposition into non-isomorphic elements of Π and that the only decomposition of an element of Π into non-isomorphic elements of Π is the obvious one. Here it is shown that there are infinitely many elements of Π even among graphs having a relatively simple structure. On the other hand, within this same class of graphs, we show that 'most' of them are not primal.

AB - It has previously been shown that there is a unique set Π of primal graphs such that every graph has an edge-decomposition into non-isomorphic elements of Π and that the only decomposition of an element of Π into non-isomorphic elements of Π is the obvious one. Here it is shown that there are infinitely many elements of Π even among graphs having a relatively simple structure. On the other hand, within this same class of graphs, we show that 'most' of them are not primal.

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

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

U2 - 10.1016/0012-365X(91)90133-M

DO - 10.1016/0012-365X(91)90133-M

M3 - Article

AN - SCOPUS:44949277808

SN - 0012-365X

VL - 87

SP - 237

EP - 248

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 3

ER -

Primal graphs with small degrees

Abstract

Bibliographical note

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this