Vol. 22, No. 2, 1967

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 329: 1
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Online Archive
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author index
To appear
Other MSP journals
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