On the fractional intersection number of a graph

DOI10.1007/S003730050068MaRDI QIDQ1808721zbMATH OpenOpenAlexFDO

Authors Edward Scheinerman, Ann Trenk

Publication date 25 November 1999

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s003730050068

zbMATH Keywords

chordal graphscliquescoveringsfractional intersection numberintersection numberinterval graphslinear program relaxationpackingsrandom Bernoulli graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Linear programming (90C05) Integer programming (90C10) Programming involving graphs or networks (90C35)

Review text

The intersection number of a graph \(G\) is the size of the smallest possible set \(S\) such that the vertices of \(G\) are represented by subsets of \(S\) with edges corresponding to intersecting subsets. The intersection number can be determined as the solution to a minimization integer program, and the fractional intersection number is defined as the solution to the linear program relaxation of this integer program. Intersection numbers and fractional intersection numbers are considered for chordal graphs, interval graphs and random Bernoulli graphs.

Recommendations

• On the intersection number of a graph
• scientific article; zbMATH DE number 19218
• Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph
• scientific article; zbMATH DE number 1339494

Cited in

(13)

• On covering graphs by complete bipartite subgraphs
• Paired threshold graphs
• Fractional L-intersecting families
• On the triangle clique cover and \(K_t\) clique cover problems
• Some lower bounds for the \(L\)-intersection number of graphs
• Computing square roots of trivially perfect and threshold graphs
• The complexity of the positive semidefinite zero forcing
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
• The intersection number of complete r-partite graphs
• On the intersection number of a graph
• On the complexity of the positive semidefinite zero forcing number
• Edge clique covers in graphs with independence number two
• Graph models for scheduling systems with machine saturation property

This page was built for publication: On the fractional intersection number of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1808721)