A Theorem on Indifference Graphs

  • Kieran Hilmer San Diego State University
  • Rom Pinchasi Technion - IIT, Haifa
  • Vadim Ponomarenko San Diego State University
Keywords: indifference graph; interval graph; intersection graph; numerical monoid; numerical semigroup

Abstract

An indifference graph P has as vertices a set of points on the real line, with an edge between every two points at most 1 apart.  For every point x in P, we set N(x) to be the set of points that are adjacent to x.   Fix an indifference graph P, and a positive integer k.  Suppose that for every x in P, k divides |N(x)|.  We show that the number of points in P is also divisible by k.

Author Biographies

Kieran Hilmer, San Diego State University

undergraduate student

Vadim Ponomarenko, San Diego State University

Professor in the Department of Mathematics and Statistics

Published
2021-08-16
How to Cite
Hilmer, K., Pinchasi, R., & Ponomarenko, V. (2021). A Theorem on Indifference Graphs. The PUMP Journal of Undergraduate Research, 4, 161-167. https://doi.org/10.46787/pump.v4i0.2613