All Lobsters with Perfect Matchings are Graceful |
| |
| Institution: | 1. Fisheries Department, Faculty of Natural Resources, Urmia University, Urmia, Iran;2. Young Researchers and Elites Club, North Tehran Branch, Islamic Azad University, Tehran, Iran;3. Rajaei Sturgeon Hatchery Center, Sari, Iran;4. Fisheries Department, Faculty of Agriculture and Natural Resources, Persian Gulf University, Bushehr, Iran;5. Medicine Laboratory, Alavi Educational and Treatment Center, Ardabil University of Medical Sciences, Ardabil, Iran;6. Biotechnology Laboratory, Faculty of Agriculture and Natural Resources, Tehran University, Karaj, Iran;1. ICE-TCS, School of Computer Science, Reykjavik University, Iceland;2. Department of Computer Science, Centre for Discrete Mathematics and its Applications (DIMAP), University of Warwick, Coventry, UK |
| |
| Abstract: | Given a tree, T, consider one of its longest paths, PT, not necessarily unique. We define T to be m–distant if no vertices of T are a distance greater than m away from PT. We will show that all 3–distant graphs are graceful, providing they satisfy the following properties.- 1.They have perfect matchings.
- 2.They can be constructed by attaching paths of length 2 to the vertices of a 1–distant tree (caterpillar), by the identification of their end vertices.
A consequence of this is that all 2–distant trees (lobsters) having perfect matchings are graceful. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
