跳图的平面性

作     者：安志华 

作者单位：新疆大学 

学位级别：硕士

导师姓名：宝音都仍

授予年度：2010年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：平面图 跳图 

摘      要：设图G是一个简单图.图G的线图L(G)以图G的边集作为顶点集, L(G)的两个顶点相邻当且仅当它们在图G中相邻. Chartrand等[2]引进了一类变换图Jk(G),称作图G的k-跳图. Jk(G)的顶点集为G的所有k条边的子图构成;两个顶点H和F在Jk(G)中相邻当且仅当G中存在四个不同的顶点u, v, w和x使得uv∈E(F), wx∈E(G)?E(F)并且H = F ?uv+wx.显然, J1(G) = L(G),并J1(G)被称作跳图.事实上,跳图有许多很好的性质,例如它的直径很小而连通度却很大. Chartrand等[2]证明了一个连通的跳图的直径不超过4. Wu和Meng [12]证明了一个连通的跳图的连通度至少比它的最小度小1,并给出了一个跳图是哈密尔顿的充要条件. Wu等[11]给出了一个图G的跳图分别是Supper-connected和hyper-connected跳图的充要条件. H′ector Hevia等人在文献[5]中刻画了所有的平面图J2(G). Chartrand等[3]刻画了迭跳图的平面性. 2004年Wei和Liu [10]刻画了平面的3,4-跳图的平面. 本文中,我们给出了跳图为平面图的充要条件. 本文分为两章,第一章是引言部分,介绍了文章的基本概念、背景和主要结果. 第二章是定理的证明部分,分为两节.第一节介绍了本文用到的定理及推论.第二节是定理的详细证明过程.