具有八个节点的自补图

In this note we deduce that there are exactly 10 self complement graphs on 8 vertices (G=G), which is characterized in the sort of degree sequences . It is a correction to the assertation made by Harary ( [ 1 ]) .     

正则的哈密顿路图

本文仅考虑无向简单图。所谓图G的哈密顿路图是指这样的图,它与G有相同的节点集,其中任意两个节点有边相连当且仅当它们在G中有哈密顿路相连。用H(G)表示图G的哈密顿路图。递归地,由H~k(G)=H(H~(k-1)(G))(k≥2)可以定义k-哈密顿路图。用ε(G)表示图G的边数。如果G(?)H~k(G),则称图G为k-自哈密顿路图,简称为k-SHP图(k-Self Hamil-tonian Path Graph(k≥1)。若k=1,则称G为SHP图。     

关于哈密顿路图

本文加强了 Chartrand,Kapoor 和 Nordhaus 等人的关于哈密顿路图的猜想的结果.由此得到一个有趣的推论:对任给 p 阶图 G,总存在一个自然数 m,使得 H~m(G)(m 重哈密顿路图)为 Chartrand 等人的猜想中所列的某类图.