Set labelling vertices to ensure adjacency coincides with disjointness

DOI10.1016/J.ENDM.2017.11.019MaRDI QIDQ2413366zbMATH OpenOpenAlexFDO

Authors Mahipal Jadeja, R. Muthu, V. Sunitha

Publication date 10 April 2018

Full work available at URL https://arxiv.org/abs/1602.04076

zbMATH Keywords

intersection graphsintersection numberKneser graphsset labellingvertex labelling

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: Given a set of nonempty subsets of some universal set, their intersection graph is defined as the graph with one vertex for each set and two vertices are adjacent precisely when their representing sets have non-empty intersection. Sometimes these sets are finite, but in many well known examples like geometric graphs (including interval graphs) they are infinite. One can also study the reverse problem of expressing the vertices of a given graph as distinct sets in such a way that adjacency coincides with intersection of the corresponding sets. The sets are usually required to conform to some template, depending on the problem, to be either a finite set, or some geometric set like intervals, circles, discs, cubes etc. The problem of representing a graph as an intersection graph of sets was first introduced by Erdos and they looked at minimising the underlying universal set necessary to represent any given graph. In that paper it was shown that the problem is NP complete. In this paper we study a natural variant of this problem which is to consider graphs where vertices represent distinct sets and adjacency coincides with disjointness. Although this is really the same problem on the complement graph, for specific families of graphs this is a more natural way of viewing it. When taken across the spectrum of all graphs the two problems are evidently identical. Our motivation to look at disjointness instead of intersection is that several well known graphs like the Petersen graph and Knesser graphs are expressed in the latter method, and the complements of these families are not well studied. The parameters we take into account are the maximum size of an individual vertex label, minimum universe size possible (disregarding individual label sizes) and versions of these two where it is required that each vertex gets labels of the same size.

Recommendations

• Set intersection representations for almost all graphs
• scientific article; zbMATH DE number 3880761
• scientific article; zbMATH DE number 7219310
• The Representation of a Graph by Set Intersections
• Uniform intersection set-labelings of a graph. I: Regularisable graphs

Cites work

• Covering graphs by the minimum number of equivalence relations
• Crossing Number is NP-Complete
• scientific article; zbMATH DE number 2141601 (Why is no real title available?)
• Kneser graphs are Hamiltonian for \(n\geq 3k\)
• Kneser's conjecture, chromatic number, and homotopy
• More odd graph theory
• The multichromatic numbers of some Kneser graphs
• The Representation of a Graph by Set Intersections
• Topics in Intersection Graph Theory

This page was built for publication: Set labelling vertices to ensure adjacency coincides with disjointness

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