Hostname: page-component-7b7567c8c-8tzhz Total loading time: 0 Render date: 2026-11-19T07:20:24.330Z Has data issue: false hasContentIssue false

Extremal Point and Edge Sets in n-Graphs

Published online by Cambridge University Press:  20 November 2018

N. Sauer*
Affiliation:
University of Calgary, Calgary, Alberta
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A set of points (edges) of a graph is independent if no two distinct members of the set are adjacent. Gallai (1) observed that, if A 0 (B 0) is the minimum number of points (edges) of a finite graph covering all the edges (points) and A 1 (B 1) is the maximum number of independent points (edges), then:

holds, where m is the number of points of the graph.

The concepts of independence and covering are generalized in various ways for n-graphs. In this paper we establish certain connections between the corresponding extreme numbers analogous to the above result of Gallai.

Ray-Chaudhuri considered (2) independence and covering problems in n-graphs and determined algorithms for finding the minimal cover and some associated numbers.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1969