Primal graphs with small degrees

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

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 languageEnglish
Pages (from-to)237-248
Number of pages12
JournalDiscrete Mathematics
Issue number3
StatePublished - 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.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Primal graphs with small degrees'. Together they form a unique fingerprint.

Cite this