On Chordal-$k$-Generalized Split Graphs
Andreas Brandstädt Raffaele Mosca






On Chordal-k-Generalized Split Graphs
    
Andreas Brandstädt

Institut für Informatik, Universität Rostock, D-18051 Rostock, Germany



Raffaele Mosca

Dipartimento di Economia, Universitá degli Studi “G. D'Annunzio”, 
Pescara 65121, Italy



    December 30, 2023
=============================================================================================================================================================================================================




A graph G is a chordal-k-generalized split graph if G is chordal and there is a clique Q in G such that every connected component in G[V ∖ Q] has at most k vertices. Thus, chordal-1-generalized split graphs are exactly the split graphs. 

We characterize chordal-k-generalized split graphs by forbidden induced subgraphs. Moreover, we characterize a very special case of chordal-2-generalized split graphs for which the Efficient Domination problem is -complete.    


Keywords:
Chordal graphs;
split graphs;
partitions into a clique and connected components of bounded size;
forbidden induced subgraphs;
-completeness; 
polynomial time recognition.




§ INTRODUCTION


G=(V,E) is a split graph if V can be partitioned into a clique and an independent set. 
The famous class of split graphs was characterized by Főldes and Hammer in <cit.> as the class of 2K_2-free chordal graphs, i.e., the class of (2K_2,C_4,C_5)-free graphs, 
and G is a split graph if and only if G and its complement graph G are chordal.

There are various important kinds of generalizations of split graphs: 
G is unipolar if there is a clique Q in G such that G[V ∖ Q] is the disjoint union of cliques of G, i.e., G[V ∖ Q] is P_3-free.
Clearly, not every unipolar graph is chordal. G is called a generalized split graph <cit.> if either G or G is unipolar.  
Generalized split graphs are perfect, and Prömel and Steger <cit.> showed that almost all perfect graphs are generalized split graphs.

We consider a different kind of generalizing split graphs: A graph G is a chordal-k-generalized split graph if G is chordal and there is a clique Q in G such that every connected component in G[V ∖ Q] has at most k vertices; we call such a clique Q a k-good clique of G. Thus, chordal-1-generalized split graphs are exactly the split graphs. 
We characterize chordal-k-generalized split graphs by forbidden induced subgraphs.    



An induced matching M ⊆ E is a set of edges whose pairwise distance in G is at least two. 
A hereditary induced matching (h.i.m.) is the induced subgraph of an induced matching, i.e., every connected component has at most two vertices, i.e., 
it is the disjoint union of an independent vertex set S and the vertex set of an induced matching M in G. 

Thus, G is a chordal-2-generalized split graph if and only if G has a clique Q such that G[V ∖ Q] is a hereditary induced matching.



§ BASIC NOTIONS AND RESULTS


For a vertex v ∈ V, N(v)={u ∈ V: uv ∈ E} denotes its (open) neighborhood, and N[v]={v}∪ N(v) denotes its closed neighborhood. A vertex v sees the vertices in N(v) and misses all the others.
The non-neighborhood of a vertex v is N(v):=V ∖ N[v].
For U ⊆ V, N(U):= ⋃_u ∈ U N(u) ∖ U and N(U):=V ∖(U ∪ N(U)).   



For a set F of graphs, a graph G is called F-free if G contains no induced subgraph isomorphic to a member of F.
In particular, we say that G is H-free if G is {H}-free.
Let H_1+H_2 denote the disjoint union of graphs H_1 and H_2, and for k ≥ 2, let kH denote the disjoint union of k copies of H.
For i ≥ 1, let P_i denote the chordless path with i vertices, and let K_i denote the complete graph with i vertices (clearly, P_2=K_2).
For i ≥ 4, let C_i denote the chordless cycle with i vertices. A graph G is chordal if it is C_i-free for any i ≥ 4. 



H is a butterfly (see Figure <ref>) if H has five vertices, say v_1,…,v_5 such that v_1,v_2,v_3 induce a K_3 and v_3,v_4,v_5 induce a K_3, and there is no other edge in H. 
H is an extended butterfly (see Figure <ref>) if H has six vertices, say v_1,…,v_6 such that v_1,v_2,v_3 induce a K_3 and v_4,v_5,v_6 induce a K_3, and the only other edge in H is v_3v_4.

H is an extended co-P (see Figure <ref>) if H has six vertices, say v_1,…,v_6 such that v_1,…,v_5 induce a P_5 and 
v_6 is only adjacent to v_1 and v_2. 

H is a chair if H has five vertices, say v_1,…,v_5 such that v_1,…,v_4 induce a P_4 and v_5 is only adjacent to v_3. 
H is an extended chair (see Figure <ref>) if H has six vertices, say v_1,…,v_6 such that v_1,…,v_5 induce a
chair as above and v_6 is only adjacent to v_1 and v_2. 

H is a gem if H has five vertices, say v_1,…,v_5 such that v_1,…,v_4 induce a P_4 and v_5 is adjacent to v_1,v_2,v_3, and v_4.
  
H is a double-gem (see Figure <ref>) if H has six vertices, say v_1,…,v_6 such that v_1,…,v_5 induce a gem, say with P_4 (v_1,v_2,v_3,v_4) and v_6 is only adjacent to v_3 and v_4.  




We say that for a vertex set X⊆ V, a vertex v ∉ X has a join (resp., co-join) to X if X⊆ N(v) (resp., X⊆N(v)).
Join (resp., co-join) of v to X is denoted by v  X (resp., v  X); if v  X then v is universal for X. Correspondingly, for vertex sets X,Y ⊆ V with X ∩ Y = ∅,
X  Y denotes x  Y for all x ∈ X and X  Y denotes x  Y for all x ∈ X. A vertex x ∉ U contacts U if x has a neighbor in U. For vertex sets U,U' with U ∩ U' = ∅, U contacts U' if there is a vertex in U contacting U'.   



As a first step for our results, we show:


If G=(V,E) is a chordal graph, Q is a clique in G and Z is a connected component in G[V ∖ Q] such that every vertex q ∈ Q has a neighbor in Z then there is a universal vertex z ∈ Z for Q, i.e., z  Q.


Proof.
We show inductively for Q={q_1,…,q_k} that there is a z ∈ Z with z  Q: 

If k=1 then trivially, there is such a vertex z ∈ Z, and if k=2, say Q={q_1,q_2}, then let x,y ∈ Z be such that q_1x ∈ E and q_2y ∈ E. If xq_2 ∉ E and yq_1 ∉ E then take a shortest path P_xy between x and y in Z; clearly, since G is chordal, there is a vertex in P_xy seeing both q_1 and q_2. 
 
Now assume that the claim is true for clique Q ∖{q_k} with k-1 vertices and let x ∈ Z be a universal vertex for Q ∖{q_k}. 
If xq_k ∈ E, we are done. Thus assume that xq_k ∉ E, and let y ∈ Z with q_ky ∈ E. If xy ∈ E then, since G is chordal, clearly, y is adjacent to all q_i, 1 ≤ i ≤ k-1. Thus, assume that the distance between x and y in Z is larger than 1. Without loss of generality, let y be a neighbor of q_k in Z which is closest to x. Let P_xy be a shortest path between x and y in Z. 
Thus, q_k is nonadjacent to every internal vertex in P_xy and to x. Then, since G is chordal, y is adjacent to all q_i, 1 ≤ i ≤ k-1. 
Thus, Lemma <ref> is shown. 




§ K-GOOD CLIQUES IN CHORDAL GRAPHS




 §.§ 2K_2-free chordal graphs


For making this manuscript self-contained, let us repeat the characterization of split graphs (and a proof variant which can be generalized for k-good cliques). 

A chordal graph G is 2K_2-free if and only if G is a split graph. 


Proof. 
If G is a split graph then clearly, G is 2K_2-free chordal.



For the converse direction, assume to the contrary that for every clique Q of G, there is a connected component, say Z_Q, of G[V ∖ Q] with at least two vertices; we call such components 2-nontrivial. Since G is 2K_2-free, all other components of G[V ∖ Q] consist of isolated vertices.   

Let Q_1:={q ∈ Q: q has a neighbor in Z_Q}, and Q_2 := Q ∖ Q_1, i.e., Q_2  Z_Q. Thus, Q = Q_1 ∪ Q_2 is a partition of Q.
Since G is 2K_2-free and Z_Q is 2-nontrivial, clearly, |Q_2| ≤ 1, and there is no connected component in G[V ∖ (Q_1 ∪ Z_Q)] with at least two vertices. Thus, G[V ∖ (Q_1 ∪ Z_Q)] is an independent vertex set.

Let Q be a clique in G with smallest 2-nontrivial component Z_Q of G[V ∖ Q] with respect to all cliques in G. Clearly, Z_Q is also the nontrivial component of G[V ∖ Q_1], i.e., Z_Q_1=Z_Q. Thus, Q_1 is a clique in G with smallest 2-nontrivial component, and from now on, we can assume that every vertex in Q_1 has a neighbor in Z_Q_1. Thus, by Lemma <ref>, there is a universal vertex z ∈ Z_Q_1 for Q_1, i.e., z  Q_1.

This implies that for the clique Q':=Q_1 ∪{z}, the 2-nontrivial component Z_Q' (if there is any for Q') is smaller than the one of Q_1 which is a contradiction. Thus, Theorem <ref> is shown.


 §.§ (2P_3, 2K_3, P_3+K_3)-free chordal graphs


Clearly, a connected component with three vertices is either a P_3 or K_3, and graph G is (2P_3, 2K_3, P_3+K_3)-free chordal if and only if G is
(2P_3, 2K_3, P_3+K_3,C_4,C_5,C_6,C_7)-free. In a very similar way as for Theorem <ref>, we show:


A chordal graph G is (2P_3, 2K_3, P_3+K_3)-free if and only if G is a chordal-2-generalized split graph.


Proof. 
If G is a chordal-2-generalized split graph then clearly, G is (2P_3, 2K_3, P_3+K_3)-free chordal.



For the converse direction, assume to the contrary that for every clique Q of G, there is a connected component, say Z_Q, of G[V ∖ Q] with at least three vertices; we call such components 3-nontrivial.  

Let Q_1:={q ∈ Q: q has a neighbor in Z_Q}, and Q_2 := Q ∖ Q_1, i.e., Q_2  Z_Q. Thus, Q = Q_1 ∪ Q_2 is a partition of Q.
Since G is (2P_3, 2K_3, P_3+K_3)-free and Z_Q is 3-nontrivial, clearly, |Q_2| ≤ 2, and there is no connected component in G[V ∖ (Q_1 ∪ Z_Q)] with at least three vertices. Thus, G[V ∖ (Q_1 ∪ Z_Q)] is a hereditary induced matching.

Let Q be a clique in G with smallest 3-nontrivial component Z_Q of G[V ∖ Q] with respect to all cliques in G. Clearly, Z_Q is also the nontrivial component of G[V ∖ Q_1], i.e., Z_Q_1=Z_Q. Thus, Q_1 is a clique in G with smallest 3-nontrivial component, and from now on, we can assume that every vertex in Q_1 has a neighbor in Z_Q_1. Thus, by Lemma <ref>, there is a universal vertex z ∈ Z_Q_1 for Q_1, i.e., z  Q_1.
This implies that for the clique Q':=Q_1 ∪{z}, the 3-nontrivial component Z_Q' (if there is any for Q') is smaller than the one of Q_1 which is a contradiction. Thus, Theorem <ref> is shown.




Clearly, not every (2P_3, 2K_3, P_3+K_3)-free graph and even not every (2P_3, 2K_3, P_3+K_3, C_5,C_6,C_7)-free graph has a 3-good clique as the following example shows:

Let v_1,v_2,v_3,v_4 induce a C_4 with edges v_iv_i+1 (index arithmetic modulo 4) and let x_1,x_2,x_3 be personal neighbors of v_1,v_2,v_3 correspondingly.
Then any clique Q has only at most two vertices, and for none of them, G[V ∖ Q] is a hereditary induced matching. 



 §.§ The general case of h-good cliques in chordal graphs
 
 
As usual, for a pair of connected graphs H_1, H_2 with disjoint vertex sets, let H_1+H_2 denote the disjoint union of H_1 and H_2.  
For any natural h, let C_h denote the family of connected graphs with h vertices, and let A_h = {X + Y: X, Y ∈ C_h}. In a very similar way as for Theorems <ref> and <ref>, we can show:
 

For any natural h, chordal graph G is A_h+1-free if and only if there is a clique Q of G such that every connected component of G[V ∖ Q] has at most h vertices.
 
 
Proof. 
If G is a chordal graph with a clique Q of G such that every connected component of G[V ∖ Q] has at most h vertices, then clearly, G is A_h+1-free chordal.



For the converse direction, assume to the contrary that for every clique Q of G, there is a connected component,  say Z_Q, of G[V ∖ Q] with at least h+1 vertices; we call such components (h+1)-nontrivial.  

Let Q_1:={q ∈ Q: q has a neighbor in Z_Q}, and Q_2 := Q ∖ Q_1, i.e., Q_2  Z_Q. Thus, Q = Q_1 ∪ Q_2 is a partition of Q.
Since G is A_h+1-free and Z_Q is (h+1)-nontrivial, clearly, |Q_2| ≤ h, and there is no connected component in G[V ∖ (Q_1 ∪ Z_Q)] with at least h+1 vertices. Thus, every connected component of G[V ∖ (Q_1 ∪ Z_Q)] has at most h vertices.

Let Q be a clique in G with smallest (h+1)-nontrivial component Z_Q of G[V ∖ Q] with respect to all cliques in G. Clearly, Z_Q is also the nontrivial component of G[V ∖ Q_1], i.e., Z_Q_1=Z_Q. Thus, Q_1 is a clique in G with smallest (h+1)-nontrivial component, and from now on, we can assume that every vertex in Q_1 has a neighbor in Z_Q_1. Thus, by Lemma <ref>, there is a universal vertex z ∈ Z_Q_1 for Q_1, i.e., z  Q_1.

This implies that for the clique Q':=Q_1 ∪{z}, the (h+1)-nontrivial component Z_Q' (if there is any for Q') is smaller than the one of Q_1 which is a contradiction. Thus, Theorem <ref> is shown.


Concerning the recognition problem, Tyshkevich and Chernyak <cit.> showed that unipolar graphs can be recognized in O(n^3) time. This time bound was slightly improved in <cit.>, and in <cit.>, McDiarmid and Yolov give a O(n^2) time recognition algorithm for unipolar graphs and generalized split graphs.
Clearly, for each fixed k, chordal-k-generalized split graphs can be recognized in O(n m) time since chordal graphs have at most n maximal cliques,  and for each of them, say Q, it can be checked in linear time whether the connected components of G[V ∖ Q] have at most k vertices.
 


§ CHARACTERIZING SPLIT-MATCHING-EXTENDED GRAPHS
 

G=(V,E) is a split-matching-extended graph if V can be partitioned into a clique Q, an independent vertex set S_Q and the vertex set of an induced matching M_Q in G such that S_Q  V(M_Q) and for every edge xy ∈ M_Q, at most one of x,y has neighbors in Q 
(note that S_Q ∪ V(M_Q) is a hereditary induced matching in G). Clearly, split-matching-extended graphs are chordal. Thus, split-matching-extended graphs are a 
special case of chordal-2-generalized split graphs. 

Clearly, split-matching-extended graphs can be recognized in linear time since for every edge xy ∈ M, the degree of x or y is 1, and deleting all such vertices of degree 1 leads to a split graph (which can be recognized in linear time). 



Various algorithmic problems such as Hamiltonian Circuit and Minimum Domination are -complete for split graphs. Efficient Domination, however, is solvable in polynomial time (even in linear time <cit.>) for split graphs while it is -complete for split-matching-extended graphs (see e.g. <cit.>). 



As mentioned in <cit.>, the graph G_H in the reduction of Exact Cover 3XC to Efficient Domination is (2P_3, K_3+P_3, 2K_3, butterfly, extended butterfly, extended co-P, extended chair, double-gem)-free chordal (and clearly, a special kind of unipolar graphs). Clearly, 2P_3-free implies C_k-free for each k ≥ 8. 


G is a split-matching-extended graph if and only if G is (C_4, C_5, C_6, C_7, 2P_3, K_3+P_3, 2K_3, butterfly, extended butterfly, extended co-P, extended chair, double-gem)-free. 


Proof.
Clearly, if G is a split-matching-extended graph then G is (C_4, C_5, C_6, C_7, 2P_3, K_3+P_3, 2K_3, butterfly, extended butterfly, extended co-P, extended chair, double-gem)-free. 



For the other direction, assume that G is (C_4,C_5,C_6,C_7,2P_3, K_3+P_3, 2K_3, butterfly, extended butterfly, extended co-P, extended chair, double-gem)-free. Then by Theorem <ref>, G has a 2-good clique Q such that G[V ∖ Q] is a hereditary induced matching, say with independent vertex set S_Q={s_1,…,s_k} and induced matching M_Q={x_1y_1,…,x_ℓy_ℓ}. Let Q be a maximum 2-good clique of G.


For every edge xy ∈ E with x,y ∈ N(Q), N_Q(x) ⊆ N_Q(y) and correspondingly for the non-neighborhoods, N_Q(y) ⊆N_Q(x) or vice versa, and in particular, x and y have a common neighbor and a common non-neighbor in Q.


Proof. 
The claim obviously holds since G is chordal and Q is maximum.  
♢


For every edge xy ∈ E with x,y ∈ N(Q), x and y have exactly one common non-neighbor in Q. 


Proof. Recall that by Claim <ref>, x and y have a common neighbor, say q_xy∈ Q, and 
suppose to the contrary that x and y have two common non-neighbors, say q_1,q_2 ∈ Q, q_1 ≠ q_2. Then x,y,q_xy,q_1,q_2 induce a butterfly in G which is a contradiction. 
Thus, Claim <ref> is shown.  
♢


For every edge xy ∈ E with x,y ∈ N(Q), at least one of x and y has at least two non-neighbors in Q. Moreover, if N_Q(x) ⊆ N_Q(y) then y has exactly one non-neighbor in Q, and thus, N_Q(x) ⊂ N_Q(y). 


Proof. 
If both x and y would have exactly one non-neighbor, say q_x,q_y ∈ Q with xq_x ∉ E and yq_y ∉ E then by Claim <ref>, 
q_x=q_y and now, (Q ∖{q_x}) ∪{x,y} would be a larger clique in G but Q is assumed to be a maximum clique in G. Thus, at least one of x,y has at least two non-neighbors in Q. 

By Claim <ref>, we have the corresponding inclusions of neighborhoods and non-neighborhoods in Q. 
If N_Q(x) ⊆ N_Q(y) and y has two non-neighbors in Q then also x has these non-neighbors but this contradicts 
Claim <ref>.
♢ 


G[N(Q)] is 2K_2-free. 


Proof. Suppose to the contrary that G[N(Q)] contains 2K_2, say xy,x'y' with xy ∈ E and x'y' ∈ E. Let z ∈ Q be a common neighbor of x,y, and let z' ∈ Q be a common neighbor of x',y'. If z=z' then x,y,x',y',z induce a butterfly. Thus, z ≠ z' for any common neighbors z of xy, z' of x'y'. If x',y' miss z and x,y miss z' then x,y,x',y',z,z' induce an extended butterfly. If x',y' miss z but exactly one of x,y, say x, sees z' then x,z,x',y',z' induce a butterfly. If exactly one of x,y, say x, sees z' and exactly one of x',y', say x', sees z then  
x,y,z,z',x',y' induce a double-gem. Thus, in any case we get a contradiction, and Claim <ref> is shown.  
♢



Thus, for at most one of the edges x_iy_i ∈ M_Q, both x_i and y_i have a neighbor in Q; without loss of generality, assume that x_1 and y_1 have a neighbor in Q, and for all other edges x_jy_j ∈ M_Q, j ≥ 2, y_j  Q. By Claim <ref>, let without loss of generality 
N_Q(x_1) ⊆ N_Q(y_1), and let u ∈ Q be a common neighbor of x_1 and y_1. 
By Claim <ref>, y_1 has exactly one non-neighbor, say z, in Q (which also misses x_1).   
Since G is extended-co-P-free and butterfly-free, and by definition, z {y_1,…,y_ℓ}, we have z {x_1,…,x_ℓ}, 
and since G is extended-chair-free and butterfly-free, z has at most one neighbor in S_Q. 

Let Q':= (Q ∖{z}) ∪{y_1}; clearly, Q' is a clique in G. Then according to Q', G is a split-matching-extended graph, and thus, Theorem <ref> is shown. 




Note added in proof.
After writing this manuscript, we learnt that actually, the results of this manuscript are not new; they follow from previous papers of Gagarin <cit.> and of Zverovich <cit.>. Sorry for that! 



99

BraMos2016
    A. Brandstädt and R. Mosca,
    Weighted efficient domination for P_5-free and P_6-free graphs,
    extended abstract in: Proceedings of WG 2016, P. Heggernes, ed., LNCS 9941, pp. 38-49, 2016. Full version:  
    SIAM J. Discrete Math. 30, 4 (2016) 2288-2303.
 
 BraMos2017
    A. Brandstädt and R. Mosca,
    On efficient domination for some classes of H-free chordal graphs,
    CoRR arXiv:1701.03414, 2017.
    
EkiHelStadeW2008
  T. Ekim, P. Hell, J. Stacho, and D. de Werra,
  Polarity of chordal graphs,
  Discrete Applied Mathematics 156 (2008) 2469-2479.
  
EscWan2014
  E.M. Eschen and X. Wang,
  Algorithms for unipolar and generalized split graphs,
  Discrete Applied Mathematics 162 (2014) 195-201.

FoeHam1977
S. Főldes and P.L. Hammer,
    Split graphs,
    Congressus Numerantium 19 (1977) 311-315.

Gagar1999
    A.V. Gagarin, Chordal (1,b)-polar graphs (in Russian), 
   Vestsi Nats. Akad. Navuk Belarusi Ser. Fiz.-Mat. Navuk 4 (1999) 115-118.

McDYol2016
  C. McDiarmid and N. Yolov,
  Recognition of unipolar and generalised split graphs,
  CoRR arXiv:1604.00922 (2016).

ProSte1992
H.J. Prömel and A. Steger,
    Almost all Berge graphs are perfect,
    Combinatorics, Probability and Computing 1 (1992) 53-79.

TysChe1985
  R.I. Tyshkevich and A.A. Chernyak,
  Algorithms for the canonical decomposition of a graph and recognizing polarity,
  Izvestia Akademii Nauk BSSR, ser. Fiz. Mat. Nauk 6 (1985) 16-23 (in Russian).
  
Zvero2006
  I.E. Zverovich, Satgraphs and independent domination. Part 1, 
  Theoretical Computer Science 352 (2006) 47-56.






