On graphs determining links with maximal number of components via medial construction |
| |
Authors: | Xian an Jin, Fengming Dong,Eng Guan Tay |
| |
Affiliation: | aSchool of Mathematical Sciences, Xiamen University, Xiamen 361005, PR China;bMathematics and Mathematics Education, National Institute of Education, Nanyang Technological University, Singapore 637616, Singapore |
| |
Abstract: | Let G be a connected plane graph, D(G) be the corresponding link diagram via medial construction, and μ(D(G)) be the number of components of the link diagram D(G). In this paper, we first provide an elementary proof that μ(D(G))≤n(G)+1, where n(G) is the nullity of G. Then we lay emphasis on the extremal graphs, i.e. the graphs with μ(D(G))=n(G)+1. An algorithm is given firstly to judge whether a graph is extremal or not, then we prove that all extremal graphs can be obtained from K1 by applying two graph operations repeatedly. We also present a dual characterization of extremal graphs and finally we provide a simple criterion on structures of bridgeless extremal graphs. |
| |
Keywords: | Plane graph Link diagram Component number Extremal characterization |
本文献已被 ScienceDirect 等数据库收录! |
|