Decomposition of Graphs into Paths and Cycles | Zendy

S. Arumugam | Zendy; I. Sahul Hamid | Zendy; V. M. Abraham | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Decomposition of Graphs into Paths and Cycles

Author(s) -

S. Arumugam,

I. Sahul Hamid,

V. M. Abraham

Publication year - 2013

Publication title -

journal of discrete mathematics

Language(s) - English

Resource type - Journals

eISSN - 2090-9837

pISSN - 2090-9845

DOI - 10.1155/2013/721051

Subject(s) - path (computing) , decomposition , mathematics , combinatorics , cardinality (data modeling) , longest path problem , induced path , disjoint sets , directed acyclic graph , decomposition method (queueing theory) , enhanced data rates for gsm evolution , discrete mathematics , graph , shortest path problem , computer science , ecology , telecommunications , data mining , biology , programming language

A decomposition of a graph is a collection of edge-disjoint subgraphs of such that every edge of belongs to exactly one . If each is a path or a cycle in , then is called a path decomposition of . If each is a path in , then is called an acyclic path decomposition of . The minimum cardinality of a path decomposition (acyclic path decomposition) of is called the path decomposition number (acyclic path decomposition number) of and is denoted by() (()). In this paper we initiate a study of the parameter anddetermine the value of for some standard graphs. Further, we obtainsome bounds for and characterize graphs attaining the bounds. Wealso prove that the difference between the parameters and can be made arbitrarily large

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research