Decomposition of bipartite graphs into closed trails

Title:

Decomposition of bipartite graphs into closed trails

Creator:

Cichacz, Sylwia and Horňák, Mirko

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:7ade0287-cd35-4b90-bff8-fcbd3a69411b
uuid:7ade0287-cd35-4b90-bff8-fcbd3a69411b

Subject:

even graph, closed trail, graph arbitrarily decomposable into closed trails, and bipartite graph

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

Let ${\rm Lct}(G)$ denote the set of all lengths of closed trails that exist in an even graph $G$. A sequence $(t_1,\dots ,t_p)$ of elements of ${\rm Lct}(G)$ adding up to $|E(G)|$ is $G$-realisable provided there is a sequence $(T_1,\dots ,T_p)$ of pairwise edge-disjoint closed trails in $G$ such that $T_i$ is of length $t_i$ for $i=1,\dots ,p$. The graph $G$ is arbitrarily decomposable into closed trails if all possible sequences are $G$-realisable. In the paper it is proved that if $a\ge 1$ is an odd integer and $M_{a,a}$ is a perfect matching in $K_{a,a}$, then the graph $K_{a,a}-M_{a,a}$ is arbitrarily decomposable into closed trails.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

129-144

Source:

Czechoslovak Mathematical Journal | 2009 Volume:59 | Number:1

Harvested from:

CDK

Metadata only:

false