liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Pk+1-Decompositions of Eulerian Graphs: Complexity and Some Solvable Cases
Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Applied Mathematics.
Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Applied Mathematics.
2003 (English)In: Electronic Notes in Discrete Mathematics, ISSN 1571-0653, Vol. 13Article in journal (Refereed) Published
Abstract [en]

We consider the problem of PMk+1-decomposition of a simple eulerian graph G, that is, decomposition of G into edge disjoint paths of length k. We show that the problem of deciding whether there exists a Pk+1 - decomposition of an eulerian simple graph is NP-complete, for every k = 3. However we find some new classes of graphs where the problem of P4-decomposition can be solved polynomially. We show that an eulerian simple graph G on 3m = 6 edges admits a P4-decomposition if G has no cut vertex v such that exactly one of the components in the graph G - ? has two vertices. In particular, this implies that a 2-connected eulerian simple graph G on 3m = 6 edges admits a P4 -decomposition. © 2003.

Place, publisher, year, edition, pages
2003. Vol. 13
Keyword [en]
eulerian graph, NP-complete, path decomposition, pendant triangle
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-46685DOI: 10.1016/S1571-0653(04)00426-3OAI: oai:DiVA.org:liu-46685DiVA: diva2:267581
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2011-01-13

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Asratian, ArmenOksimets, Natalia

Search in DiVA

By author/editor
Asratian, ArmenOksimets, Natalia
By organisation
The Institute of TechnologyApplied Mathematics
In the same journal
Electronic Notes in Discrete Mathematics
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 253 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf