Search

Start Over Creator Che, Zhongyuan

1. Existence of perfect matchings in a plane bipartite graph

Creator:
Che, Zhongyuan
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
elementary edge-cut, hexagonal system, perfect matching, and plane bipartite graph
Language:
English
Description:
We give a necessary and sufficient condition for the existence of perfect matchings in a plane bipartite graph in terms of elementary edge-cut, which extends the result for the existence of perfect matchings in a hexagonal system given in the paper of F. Zhang, R. Chen and X. Guo (1985).
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

2. On $k$-pairable graphs from trees

Creator:
Che, Zhongyuan
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
$k$-pairable graph;, pair length, Cartesian product, $G$-layer, and tree
Language:
English
Description:
The concept of the $k$-pairable graphs was introduced by Zhibo Chen (On $k$-pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter $p(G)$, called the pair length of a graph $G$, as the maximum $k$ such that $G$ is $k$-pairable and $p(G)=0$ if $G$ is not $k$-pairable for any positive integer $k$. In this paper, we answer the two open questions raised by Chen in the case that the graphs involved are restricted to be trees. That is, we characterize the trees $G$ with $p(G)=1$ and prove that $p(G \square H)=p(G)+p(H)$ when both $G$ and $H$ are trees.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public