On the Fractional Intersection Number of a Graph |
| |
Authors: | Edward R Scheinerman Ann N Trenk |
| |
Institution: | (1) Department of Mathematical Sciences, The Johns Hopkins University, Baltimore, MD 21218, USA. e-mail: ers@jhu.edu., TP;(2) Department of Mathematics, Wellesley College, Wellesley, MA 02181, USA e-mail: atrenk@wellesley.edu., US |
| |
Abstract: | An intersection representation of a graph G is a function f:V(G)→2S (where S is any set) with the property that uv∈E(G) if and only if f(u)∩f(v)≠∅. The size of the representation is |S|. The intersection number of G is the smallest size of an intersection representation of G. The intersection number can be expressed as an integer program, and the value of the linear relaxation of that program gives
the fractional intersection number. This is in consonance with fractional versions of other graph invariants such as matching number, chromatic number, edge
chromatic number, etc.
We examine cases where the fractional and ordinary intersection numbers are the same (interval and chordal graphs), as well
as cases where they are wildly different (complete multipartite graphs). We find the fractional intersection number of almost
all graphs by considering random graphs.
Received: July 1, 1996 Revised: August 11, 1997 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|