On Eulerian and Hamiltonian Graphs and Line Graphs
On Eulerian and Hamiltonian Graphs and Line Graphs
复制标题
DOI：
10.4153/cmb-1965-051-3
复制
发表时间：
1965-12
期刊：
影响因子：
--
通讯作者：
F. Harary;C. S. J. A. Nash-Williams
中科院分区：
文献类型：
--
作者：
F. Harary;C. S. J. A. Nash-Williams
图G有一个有限的点集V和一个线集X，每条线连接两个不同的点（称为其端点），并且没有两条线连接同一对点。只有一点而没有直线的图是平凡的。一条线与它的每一个端点相关联。如果两点由一条线连接，则它们是相邻的。G的线图L（G）以X为点集，X的两个元素x，y在L（G）中相邻，只要G的x，y有一个公共端点。图G中的游动是点和线的交替序列v1，x1，v2，x2，.，vn，第一项和最后一项是点，使得xi是连接vi和vi+1的线，其中i=1，.，n-1。
A graph G has a finite set V of points and a set X of lines each of which joins two distinct points (called its end-points), and no two lines join the same pair of points. A graph with one point and no line is trivial. A line is incident with each of its end-points. Two points are adjacent if they are joined by a line. The degree of a point is the number of lines incident with it. The line-graph L(G) of G has X as its set of points and two elements x, y of X are adjacent in L(G) whenever the lines x and y of G have a common end-point. A walk in G is an alternating sequence v1, x1, v2, x2, …, vn of points and lines, the first and last terms being points, such that xi is the line joining vi to vi+1 for i=1, …, n-1.