Vol. 22, No. 2, 1967

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 307: 1  2
Vol. 306: 1  2
Vol. 305: 1  2
Vol. 304: 1  2
Vol. 303: 1  2
Vol. 302: 1  2
Vol. 301: 1  2
Vol. 300: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Editorial Board
Subscriptions
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
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
Abstract

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
Milestones
Received: 3 December 1965
Published: 1 August 1967
Authors
Lowell Wayne Beineke
Frank Harary
Michael David Plummer