Edges not contained in triangles and the distribution of contractible edges in a 4-connected graph |
| |
| Authors: | Kiyoshi Ando |
| |
| Institution: | a Department of Information and Communication Engineering, The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu-city, Tokyo 182-8585, Japan
b Department of Mathematical Information Science, Tokyo University of Science, 1-3 Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan |
| |
| Abstract: | We prove results concerning the distribution of 4-contractible edges in a 4-connected graph G in connection with the edges of G not contained in a triangle. As a corollary, we show that if G is 4-regular 4-connected graph, then the number of 4-contractible edges of G is at least one half of the number of edges of G not contained in a triangle. |
| |
| Keywords: | 05C40 |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
