Decomposition of graphs into paths and cycles (Q2249934): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q58920037, #quickstatements; #temporary_batch_1706881316814 |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1155/2013/721051 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1984843974 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5670652 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Path-Numbers of Some Multipartite Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5628160 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5656791 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Acyclic graphoidal covers and path partitions in a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Modeling return to isotropy using kinetic equations / rank | |||
Normal rank |
Latest revision as of 18:00, 8 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decomposition of graphs into paths and cycles |
scientific article |
Statements
Decomposition of graphs into paths and cycles (English)
0 references
4 July 2014
0 references
Summary: A decomposition of a graph \(G\) is a collection \(\psi\) of edge-disjoint subgraphs \(H_1,H_2,\ldots,H_r\) of \(G\) such that every edge of \(G\) belongs to exactly one \(H_i\). If each \(H_i\) is a path or a cycle in \(G\), then \(\psi\) is called a path decomposition of \(G\). If each \(H_i\) is a path in \(G\), then \(\psi\) is called an acyclic path decomposition of \(G\). The minimum cardinality of a path decomposition (acyclic path decomposition) of \(G\) is called the path decomposition number (acyclic path decomposition number) of \(G\) and is denoted by \(\pi(G)\) (\(\pi_a(G)\)). In this paper we initiate a study of the parameter \(\pi\) and determine the value of \(\pi\) for some standard graphs. Further, we obtain some bounds for \(\pi\) and characterize graphs attaining the bounds. We also prove that the difference between the parameters \(\pi\) and \(\pi_a\) can be made arbitrarily large.
0 references
acyclic path decomposition number
0 references