patternMinor
Name of graph family defined by modular sum
Viewed 0 times
graphmodularnamesumfamilydefined
Problem
In the context of finite, simple, undirected graphs, associate with each node $v\in V$ an integer $n(v)$ (you can limit this to positive integers without loss of generality). Create the set of edges by defining a threshold $T$, and join an edge $x,y$ iff $n(x)+n(y) \geq T$. These are called threshold graphs$^{[1]}$ and they are well-studied, their structure has been characterized.
If, instead, $x,y$ are joined by an edge iff $n(x)+n(y)=0\ (mod\ T)$, we form another very simple class of graphs. But have they been studied and do they have a name?
$^{[1]}$ Chvátal, Václav; Hammer, Peter L. (1977), "Aggregation of inequalities in integer programming", in Hammer, P. L.; Johnson, E. L.; Korte, B. H.; et al. (eds.), Studies in Integer Programming (Proc. Worksh. Bonn 1975), Annals of Discrete Mathematics, vol. 1, Amsterdam: North-Holland, pp. 145–162.
If, instead, $x,y$ are joined by an edge iff $n(x)+n(y)=0\ (mod\ T)$, we form another very simple class of graphs. But have they been studied and do they have a name?
$^{[1]}$ Chvátal, Václav; Hammer, Peter L. (1977), "Aggregation of inequalities in integer programming", in Hammer, P. L.; Johnson, E. L.; Korte, B. H.; et al. (eds.), Studies in Integer Programming (Proc. Worksh. Bonn 1975), Annals of Discrete Mathematics, vol. 1, Amsterdam: North-Holland, pp. 145–162.
Solution
Your graph class is the class of graphs that are a disjoint union of a clique and a bunch of bicliques, possibly singletons.
We can safely assume that the labels $\ell(v) \in [0,T)$, and it is then clear that every pair of vertices with the same label is going to be a twin.
They will be true twins if and only if $\ell(v)=T/2$ in which case they will necessarily comprise a disjoint clique component.
Otherwise they'll be false twins fully connected to exactly one other (possibly empty) (false) twin class, i.e., they form one side of a disjoint biclique.
We can safely assume that the labels $\ell(v) \in [0,T)$, and it is then clear that every pair of vertices with the same label is going to be a twin.
They will be true twins if and only if $\ell(v)=T/2$ in which case they will necessarily comprise a disjoint clique component.
Otherwise they'll be false twins fully connected to exactly one other (possibly empty) (false) twin class, i.e., they form one side of a disjoint biclique.
Context
StackExchange Computer Science Q#164533, answer score: 4
Revisions (0)
No revisions yet.