Vol. 22, No. 2, 1967

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 290: 1  2
Vol. 289: 1  2
Vol. 288: 1  2
Vol. 287: 1  2
Vol. 286: 1  2
Vol. 285: 1  2
Vol. 284: 1  2
Vol. 283: 1  2
Online Archive
The Journal
Editorial Board
Special Issues
Submission Guidelines
Submission Form
Author Index
To Appear
ISSN: 0030-8730
On the critical lines of a graph

Lowell Wayne Beineke, Frank Harary and Michael David Plummer

Vol. 22 (1967), No. 2, 205–212

A set of points M is said to cover a graph G if every line in G has at least one point in M. Call M a minimum cover (m.c.) for G if it is a point cover with a minimum number of points. The number of points in any minimum cover of a graph G is called the point covering number of G and is denoted by α(G). If x is a line in G, denote by G x the graph obtained from G by deleting x. Similarly, if v is a point of G,Gv will denote the graph obtained from G by deleting v and all lines incident with v. A line x in G is said to be a critical line (with respect to point covering) if α(G x) < α(G). A graph is called line-critical if every line is critical. Obviously every complete graph is line-critical, and so is any odd cycle. There are, however, many other line-critical graphs. The main purpose of this paper is to prove that in any graph, two adjacent critical lines must lie on an odd cycle. This result will imply that a line-critical graph must be a block and furthermore, that any two adjacent lines in such a graph must lie on an odd cycle.

Mathematical Subject Classification
Primary: 05.40
Received: 3 December 1965
Published: 1 August 1967
Lowell Wayne Beineke
Frank Harary
Michael David Plummer