A split graph is a graph in which the vertices can be partitioned into an independent set and a clique. We show that every nonsplit graph has at most four split maximal proper edge induced subgraphs. The exhaustive list of fifteen classes of nonsplit graphs having a split maximal proper edge induced subgraph is determined in this paper.
All graphs considered in this paper are finite, simple and undirected. We shall denote the set of vertices by \(V(G)\) and the set of edges by \(E(G).\) Terms not defined here are taken as in [12]. The subgraph of \(G\) induced by a vertex subset \(S\) is denoted by \(\langle S \rangle.\) The set of all vertices adjacent to \(v\) in \(G\) is denoted by \(N_G(v)\) and it is called the neighborhood of \(v\) in \(G\) and \(N_G[v] = N_G(v) \cup \{v\}.\)
The one edge deleted unlabeled subgraph \(G-e\) is called an edge card of \(G\). The edge deck of \(G,\) denoted \(ED(G),\) is the multiset of edge deleted subgraphs (edge cards) of \(G,\) and we refer to the elements of \(ED(G)\) as maximal proper edge induced subgraphs (or simply edge cards or ecards). The edge reconstruction number of \(G,\) denoted \(ERN(G),\) is the size of a smallest subset of \(ED(G)\) that determines \(G\) up to isomorphism, if such a subset exists. More precisely, if \(ERN(G) = k,\) then there are edges \(e_1, e_2,\dots, e_k\) in \(G\) such that if \(H\) is a graph with edges \(e'_1, e'_2,\dots, e'_k\) where \(G – e_i \cong H – e'_i\) for \(i = 1,2,\dots, k,\) then \(G \cong H.\) Graphs for which \(ERN(G)\) is defined, that is, those graphs that are determined by their edge deck, are said to be edge reconstructible. Edge reconstruction numbers are known for only few classes of graphs [9, 10]. The famous Edge Reconstruction Conjecture, proposed by Harary [5], asserts that every graph with at least four edges is edge reconstructible. The vertex reconstructible graphs (or simply reconstructible graphs) and the vertex reconstruction number (or simply reconstruction number, denoted by \(RN(G)\)) of a graph are defined similarly with vertex deletions instead of edge deletions. The \(RN(G)\) was first defined by Harary and Plantholt [6]. Bollobas [2] has shown that almost all graphs \(G\) (in the probabilistic sense) have \(RN(G)=3.\) Monikandan and Anu [11] have recently shown that the reconstruction number of most of the separable graphs (connected graphs with a cut vertex) with pendant vertices is three if the reconstruction number of all other connected graphs without pendant vertices is three, which strengthen the above result of Bollobas [2]. For a survey of early results on the reconstruction number problems, see [1]. The reconstruction number (edge reconstruction number) of \(G\) is expected to serve as a measure of the level of difficulty of reconstructing \(G\) from the deck (edge deck) of \(G.\)
A clique of a graph \(G\) is a vertex subset inducing a complete subgraph of \(G.\) A vertex subset \(I\) of \(G\) is called an independent set if no pair of distinct vertices of \(I\) are adjacent in \(G.\) A graph is split if the vertex set can be partitioned into an independent set and a clique. Hammer and Foldes [4] characterized split graphs as graphs \(G\) such that both \(G\) and the complement graph \(\bar{G}\) are chordal graphs (graphs in which every cycle of length at least four contains a chord). Many characterizations and properties of split graphs were obtained ([8]; Ch. 8 & 9). A graph is distance-hereditary if for all connected induced subgraphs \(F\) of \(G\), \(d_{F}(u,v) = d_G(u,v)\) for every pair of vertices \(u,v \in V(F).\) Distance-hereditary graphs were introduced by Howorka [7], who was also the first to characterize these graphs. Devi Priya and Monikandan [3] have proved a reduction that all graphs are reconstructible if the family \(\mathscr{F}\) of all non-distance hereditary 2-connected graphs \(G\) with \(diam(G)=2\) or \(diam(G)=diam(\overline{G})=3\) is reconstructible. So, any result proving or determining the possibility of the (edge) reconstructibility of a subclass of \(\mathscr{F}\) assumes importance. Many family of connected split graphs without end vertices belong to \(\mathscr{F}.\)
We show that every nonsplit graph has at most four split ecards and so if at least five ecards of a graph are split, then the graph is split. The exhaustive list of fifteen classes of nonsplit graphs having a split ecard is given, which is the main result of this paper.
The following characterization of split graphs was obtained by Foldes and Hammer[4].
Theorem 2.1. A graph is split if and only if it has no induced subgraph isomorphic to \(C_5,~C_4\) or \(2K_2.\)
Lemma 2.2. Every edge card of a nonsplit graph containing an induced subgraph isomorphic to \(C_5\) is nonsplit.
Proof. Let \(G\) be a nonsplit graph containing an induced subgraph \(T\) isomorphic to \(C_5\). For an edge \(e \in E(G)-E(T),\) the ecard \(G-e\) contains \(T\) as an induced subgraph and hence each ecard \(G-e\) is nonsplit. For an edge \(e'=ab \in E(T),\) \(\langle N_{T-e'}[\{a,b\}]\rangle\) isomorphic to \(2K_2\) and hence every ecard of \(G\) is nonsplit. ◻
As we want to list out all nonsplit graphs having split ecards, in view of the above lemma, we assume that all nonsplit graphs considered hereafter have no induced subgraph isomorphic to \(C_5\) (i.e, \(C_5-\text{free}\) nonsplit graphs).
Lemma 2.3. Every nonsplit graph has at most four split edge cards.
Proof. Let \(G\) be a nonsplit graph containing an induced subgraph \(T\) isomorphic to \(C_4\) or \(2K_2\). If an ecard, obtained by deleting an edge from a copy of \(C_4\) (or \(2K_2\)) in \(G,\) may possibly contain no induced subgraph isomorphic to \(C_4\) (or \(2K_2\)). Consequently, any nonsplit graph can have at most four edges such that the corresponding ecards may not contain \(C_4\)(or \(2K_2\)) as an induced subgraph. Since the other type have two edges of the same type, the graph \(G\) has at most four split ecards. ◻
Corollary 2.4. If an edge deck of a graph \(G\) contains five split edge cards, then the unknown parent graph \(G\) is split.
We now proceed to find all nonsplit graphs having precisely \(k\) split ecards, where \(k = 1,2,3,\) or \(4.\) As a prelude, we define few notation for the sake of clarity.
Notation 2.5. Let \(U\) and \(W\) be disjoint subsets of \(V(G).\)
(i) By \(U \sim W\) means that there is a vertex in \(U\) adjacent to at least one vertex in \(W;\)
(ii) By \(U \sim \sim W,\) we mean that every vertex in \(U\) is adjacent to every vertex in \(W;\)
(iii) By \(U \nsim W,\) we mean that there is a vertex in \(U\) not adjacent to at least one vertex in \(W;\)
(iv) By \(U \nsim \nsim W\) means that no vertex in \(U\) is adjacent to a vertex in \(W.\)
For \(U = \{u\},\) we just write \(u \sim W\) and \(u \nsim W\) instead of \(U \sim W\) and \(U \nsim W,\) respectively.
Let \(\mathscr{G}\) be the collection of all nonsplit graphs containing an induced subgraph isomorphic to \(C_4\) or \(2K_2.\). Let \(G \in \mathscr{G}\). Let \(T(G)\) be a subset of \(V(G)\) such that the subgraph induced by \(T(G)\) contains all induced subgraph isomorphic to \(C_4\) or \(2K_2.\) Then \(G-e\) is non-split for all \(e \in E(G)-E(\langle T(G) \rangle)\) and if \(G-e\) is a split ecard , then \(e \in E(\langle T(G)\rangle).\) Therefore, all the vertices (if any) of \(G\) that are not in \(T(G)\) can be partitioned into a clique \(C(G)\) and an independent set \(I(G)\), where \(C(G)\) and \(I(G)\) may be empty. That is, \(V(G)= C(G)\cup I(G) \cup T(G)\). If no confusion arises, we simply use \(T,~ C, ~ I\) instead of \(T(G),~C(G), ~I(G)\) respectively.
In view of Theorem 2.1, we have the following two properties \(P(C_4)\) and \(P(2K_2).\)
\(P(C_4):\) In a nonsplit graph \(G\) containing an induced subgraph \(\langle K \rangle \cong C_4,\) if \(G-v_1v_2\) is a split ecard, where \(v_1,v_2 \in K,\) then vertices in \(K-\{v_1,v_2\}\) must lie in the clique partition of \(G-v_1v_2\) and \(v_1\) and \(v_2\) must lie in the independent partition of \(G-v_1v_2.\)
\(P(2K_2):\) In a nonsplit graph \(G\) containing an induced subgraph \(\langle K \rangle \cong 2K_2,\) if \(G-v_1v_2\) is a split ecard, where \(v_1,v_2\in K,\) then \(v_1\) and \(v_2\) must lie in the independent partition of \(G-v_1v_2\) and one vertex in \(K-\{v_1,v_2\}\) must lie in the clique partition of \(G-v_1v_2.\)
Here we want to find a nonsplit graph \(H\) with exactly one split edge card, say \(H-e\). Being a split edge card of a nonsplit graph, \(H\) must contain an induced subgraph \(T\) isomorphic to \(C_4\) or \(2K_2\). Every ecard \(H-e'\), obtained by deleting an edge except from a copy of \(C_4\) (or \(2K_2\)) in \(H,\) must contain an induced subgraph isomorphic to \(C_4\) (or \(2K_2\)) and hence \(H-e'\) is nonsplit and the required edge \(e\) of \(H\) must lie in all induced subgraphs that are isomorphic to \(C_4\) or \(2K_2\). Thus, we can partite the collection of nonsplit graphs with exactly one split edge card as below:
In all the figures in this paper, a single line denotes the existence of an edge, a double line denotes the existence of all possible edges, dashed single line denotes nonexistence of an edge, and dashed double line denotes the nonexistence of any edge.
Let \(G_1 \in \mathscr{G}\) with \(T(G_1) = \{a_1, a_2, a_3, a_4, a_5\}\), \(a_1a_2, a_3a_4, a_4a_5 \in E(G_1)\) and \(a_1a_3, a_1a_4, a_2a_3,\) \(a_2a_4, a_1a_5, a_2a_5 \notin E(G_1)\) and let \(G_2 \in \mathscr{G}\) with \(T(G_2) = \{a_1, a_2, a_3, a_4, a_5, a_6\}\), \(a_1a_2, a_2a_3,\) \(a_3a_4, a_1a_4, a_1a_5, a_3a_5, a_3a_6 \in E(G_2)\) and \(a_1a_3, a_2a_4, a_2a_5, a_1a_6, a_2a_6 \notin E(G_2).\)
A nonsplit graph \(G\) has exactly one split ecard only if \(G\) belongs to any one of the following five subfamilies \(\mathscr{F}1i\) of graphs in \(\mathscr{G},\) for \(i=1,2,3,4,5.\)
\(\mathscr{F}11~:\) Graphs containing two induced \(C_4\) with exactly one common edge.
\(\mathscr{F}12~:\) Graphs containing two induced \(2K_2\) with exactly one common edge.
\(\mathscr{F}13~:\) Graphs containing an induced \(C_4\) and an induced \(2K_2\) with exactly one
common edge.
\(\mathscr{F}14~:\) Graphs containing \(G_1\) as an induced subgraph.
\(\mathscr{F}15~:\) Graphs containing \(G_2\) as an induced subgraph.
Let \(G_3 \in \mathscr{G}\) with
\(T(G_3) = \{a_1, a_2, a_3, a_4, a_5,
a_6\}\),
\(a_1a_2, a_2a_3, a_3a_4, a_4a_5, a_5a_6,
a_6a_1, a_1a_4\)\(\in E(G_3)\)
and \(a_1a_3, a_2a_4, a_4a_6, a_1a_5 \notin
E(G_3)\). We shall now construct \(G_3\) such that \(G_3-a_1a_4\) to be split.
\(\underline{a_1a_4 \text{-ecard}}\):
If \(a_1\) was lying in a clique partition of the maximal edge induced subgraph \(G_3-a_1a_4\), then, since \(a_1a_3, a_1a_4 \notin E(G_3-a_1a_4)\) and \(a_3a_4 \in E(G_3-a_1a_4)\), both \(a_3\) and \(a_4\) would not lie in an independent set of the maximal edge induced subgraph \(G_3-a_1a_4\), giving a contradiction by \(P(C_4)\). Therefore \(a_1\) lies in the independent set partition of the maximal edge induced subgraph \(G_3-a_1a_4\) and \(a_1 \nsim \nsim I(G_3)\). Similarly, \(a_4\) lies in the independent set partition of the maximal edge induced subgraph \(G_3-a_1a_4\) and \(a_4 \nsim \nsim I(G_3)\).
If \(a_2\) was lying in an independent partition of the maximal edge induced subgraph \(G_3-a_1a_4\), then, since \(a_1a_2, a_2a_3 \in E(G_3-a_1a_4)\) and \(a_1a_3 \notin E(G_3-a_1a_4)\), both \(a_1\) and \(a_3\) would not lie in a clique of the maximal edge induced subgraph \(G_3-a_1a_4\), giving a contradiction by \(P(C_4)\). Therefore \(a_2\) lies in the clique partition of the maximal edge induced subgraph \(G_3-a_1a_4\) and \(a_2 \sim \sim C(G_3)\). Similarly, \(a_3,a_5\) and \(a_6\) lie in the clique partition of the maximal edge induced subgraph \(G_3-a_1a_4\) and \(\{a_3,a_5,a_6\} \sim \sim C(G_3)\). Therefore, a necessary condition for \(G_3-a_1a_4\) to be a split ecard of \(G_3\) is \(\{a_2, a_3,a_5,a_6\} \sim \sim C(G_3)\) \(\&\) \(\{a_1,a_4\} \nsim \nsim I(G_3).\)
A nonsplit graph \(G_3\) has only one split ecard \(G_3-a_1a_4\) if and only if it satisfies
1C.1: \(\{a_2,a_3,a_5,a_6\} \sim \sim C(G_3),\) \(\{a_1,a_4\} \nsim \nsim I(G_3)\) and \(\{a_2, a_3\}\sim\sim\{a_5,a_6\}\) (Figure 3(i)) (The label 1C we use here to mean a condition under one split ecard case).
Let \(G_4 \in \mathscr{G}\) with \(T(G_4) = \{a_1, a_2, a_3, a_4, a_5, a_6\}\), \(a_1a_2, a_3a_4, a_5a_6\\ \in E(G_4)\) and \(a_1a_3, a_1a_4,\) \(a_2a_3,a_2a_4, a_3a_5, a_3a_6, a_4a_5, a_4a_6 \notin E(G_4)\). We shall now construct \(G_4\) such that \(G_4-a_3a_4\) to be split.
\(\underline{a_3a_4 \text{-ecard}}\):
If \(a_3\) was lying in a clique of the maximal edge induced subgraph \(G_4-a_3a_4\), then, since \(a_1a_3, a_2a_3 \notin E(G_4-a_3a_4)\) and \(a_1a_2 \in E(G_4-a_3a_4)\), both \(a_1\) and \(a_2\) would not lie in an independent set of the maximal edge induced subgraph \(G_4-a_3a_4\), giving a contradiction by \(P(2K_2)\). Therefore \(a_3\) lies in the independent set partition of the maximal edge induced subgraph \(G_4-a_3a_4\) and \(a_3 \nsim \nsim I(G_4)\). Similarly, \(a_4\) lies in the independent set partition of the maximal edge induced subgraph \(G_4-a_3a_4\) and \(a_4 \nsim \nsim I(G_4)\).
By \(P(2K_2)\), either \(a_1\) or \(a_2\) lies in the clique partition of the
maximal edge induced subgraph \(G_4-a_3a_4\), since \(\langle\{a_1,a_2,a_3,a_4\}\rangle\) \(\cong 2K_2\). Similarly, by \(P(2K_2)\), either \(a_5\) or \(a_6\) lies in the clique partition of the
maximal edge induced subgraph \(G_4-a_3a_4\). Therefore, one of the
following nine conditions (X1-X9) must be a necessary condition for the
maximal edge induced subgraph \(G_4-a_3a_4\) of \(G_4\) to be a split.
X1 : \(\{a_1, a_2, a_5, a_6\} \sim \sim
C(G_4)\) \(\&\) \(\{a_3, a_4\} \nsim \nsim I(G_4)\)
X2 : \(\{a_1, a_2, a_5\} \sim \sim C(G_4)\) \(\&\) \(\{a_3, a_4, a_6\} \nsim \nsim I(G_4)\)
X3 : \(\{a_1, a_2, a_6\} \sim \sim C(G_4)\) \(\&\) \(\{a_3, a_4, a_5\} \nsim \nsim I(G_4)\)
X4 : \(\{a_1, a_5, a_6\} \sim \sim C(G_4)\) \(\&\) \(\{a_2, a_3, a_4\} \nsim \nsim I(G_4)\)
X5 : \(\{a_2, a_5, a_6\} \sim \sim C(G_4)\) \(\&\) \(\{a_1, a_3, a_4\} \nsim \nsim I(G_4)\)
X6 : \(\{a_1, a_5\} \sim \sim C(G_4)\) \(\&\) \(\{a_2, a_3, a_4, a_6\} \nsim \nsim I(G_4)\)
X7 : \(\{a_1, a_6\} \sim \sim C(G_4)\) \(\&\) \(\{a_2, a_3, a_4, a_5\} \nsim \nsim I(G_4)\)
X8 : \(\{a_2, a_5\} \sim \sim C(G_4)\) \(\&\) \(\{a_1, a_3, a_4, a_6\} \nsim \nsim I(G_4)\)
X9 : \(\{a_2, a_6\} \sim \sim C(G_4)\) \(\&\) \(\{a_1, a_3, a_4, a_5\} \nsim \nsim I(G_4)\)
A nonsplit graph \(G_4\) has only one split ecard \(G_4-a_3a_4\) if and only if it satisfies one of the following adjacency conditions (1C.2) to (1C.4).
(1C.2:) \(\{a_1, a_2, a_5, a_6\}\sim\sim C(G_4),\{a_3, a_4\}\nsim\nsim I(G_4)\) and \(\{a_1, a_2\}\sim\sim\{a_5,a_6\}\).
(1C.3:) \(\{a_1, a_2, a_5\}\sim\sim C(G_4),\{a_3, a_4, a_6\}\nsim\nsim I(G_4)\) and \(\{a_1, a_2\}\sim\sim\{a_5\}\) (Figure 3(ii)).
(1C.4:) \(\{a_1, a_5\} \sim \sim C(G_4),\) \(\{a_2, a_3, a_4, a_6\} \nsim \nsim I(G_4),\) \(a_1 \sim a_5\) and \(a_2\nsim a_6 .\)
Let \(G_5 \in \mathscr{G}\) with
\(T(G_5) = \{a_1, a_2, a_3, a_4, a_5,
a_6\}\),
\(a_1a_2, a_2a_3, a_3a_4, a_4a_1, a_5a_6 \in
E(G_5)\) and \(a_1a_3, a_2a_4, a_1a_5,
a_1a_6, a_4a_5, a_4a_6 \notin E(G_5)\). We shall now construct
\(G_5\) such that \(G_5-a_1a_4\) to be split.
\(\underline{a_1a_4 \text{-ecard}}\):
If \(a_1\) was lying in a clique of the maximal edge induced subgraph \(G_5-a_1a_4\), then, since \(a_1a_3, a_1a_4 \notin E(G_5-a_1a_4)\) and \(a_3a_4 \in E(G_5-a_1a_4)\), both \(a_3\) and \(a_4\) would not lie in an independent set of the maximal edge induced subgraph \(G_5-a_1a_4\), giving a contradiction by \(P(C_4)\). Therefore \(a_1\) lies in the independent set partition of the maximal edge induced subgraph \(G_5-a_1a_4\) and \(a_1 \nsim \nsim I(G_5)\). Similarly, \(a_4\) lies in the independent set partition of the maximal edge induced subgraph \(G_5-a_1a_4\) and \(a_4 \nsim \nsim I(G_5)\). Similarly, by \(P(C_4)\), both \(a_2\) and \(a_3\) lie in the clique partition of the maximal edge induced subgraph \(G_5-a_1a_4\) and \(\{a_2,a_3\} \sim \sim C(G_5)\) and by \(P(2K_2),\) either \(a_5\) or \(a_6\) lies in the clique partition of the ecard \(G_5-a_1a_4\). Therefore, one of the following three conditions (Y1-Y3) must be a necessary condition for the maximal edge induced subgraph \(G_5-a_1a_4\) of \(G_5\) to be a split.
Y1 : \(\{a_2, a_3, a_5, a_6\} \sim \sim C(G_5)\) \(\&\) \(\{a_1, a_4\} \nsim \nsim I(G_5)\)
Y2 : \(\{a_2, a_3, a_5\} \sim \sim C(G_5)\) \(\&\) \(\{a_1, a_4, a_6\} \nsim \nsim I(G_5)\)
Y3 : \(\{a_2, a_3, a_6\} \sim \sim C(G_5)\) \(\&\) \(\{a_1, a_4, a_5\} \nsim \nsim I(G_5)\)
A nonsplit graph \(G_5\) has only one split ecard \(G_5-a_1a_4\) if and only if it satisfies one of the following adjacency conditions (1C.5) to (1C.6).
(1C.5:) \(\{a_2, a_3, a_5, a_6\}\sim\sim C(G_5),\{a_1, a_4\}\nsim\nsim I(G_5)\) and \(\{a_2, a_3\}\sim\sim\{a_5,a_6\}\).
(1C.6:) \(\{a_2, a_3, a_5\}\sim\sim C(G_5),\{a_1, a_4, a_6\}\nsim\nsim I(G_5)\) and \(\{a_2, a_3\}\sim\sim\{a_5\}\) (Figure 3(iii)).
Let \(G_1 \in \mathscr{G}\) with
\(T(G_1) = \{a_1, a_2, a_3, a_4,
a_5\}\), \(a_1a_2, a_3a_4, a_4a_5 \in
E(G_1)\) and \(a_1a_3, a_1a_4,\)
\(a_2a_3, a_2a_4,a_1a_5, a_2a_5 \notin
E(G_1)\). We shall now construct \(G_1\) such that \(G_1-a_1a_2\) to be split.
\(\underline{a_1a_2
\text{-ecard}}\):
If \(a_1\) was lying in a clique of the
maximal edge induced subgraph \(G_1-a_1a_2\), then, since \(a_1a_3, a_1a_4 \notin E(G_1-a_1a_2)\) and
\(a_3a_4 \in E(G_1-a_1a_2)\), both
\(a_3\) and \(a_4\) would not lie in an independent set
of the maximal edge induced subgraph \(G_1-a_1a_2\), giving a contradiction by
\(P(2K_2)\). Therefore \(a_1\) lies in the independent set partition
of the maximal edge induced subgraph \(G_1-a_1a_2\) and \(a_1 \nsim \nsim I(G_1)\). Similarly, \(a_2\) lies in the independent set partition
of the maximal edge induced subgraph \(G_1-a_1a_2\) and \(a_2 \nsim \nsim I(G_1)\). By \(P(2K_2)\), either \(a_3\) or \(a_4\) lies in the clique partition of the
maximal edge induced subgraph \(G_1-a_1a_2\), since \(\langle\{a_1,a_2,a_3,a_4\}\rangle \cong
2K_2\). Similarly, by \(P(2K_2)\), either \(a_4\) or \(a_5\) lies in the clique partition of the
ecard \(G_1-a_1a_2\). Therefore, one of
the following five conditions (Z1-Z5) must be a necessary condition for
maximal edge induced subgraph \(G_1-a_1a_2\) of \(G_1\) to be a split.
Z1 : \(\{a_3, a_4, a_5\} \sim \sim C(G_1)\) \(\&\) \(\{a_1, a_2\} \nsim \nsim I(G_1)\)
Z2 : \(\{a_3, a_4\} \sim \sim C(G_1)\) \(\&\) \(\{a_1, a_2, a_5\} \nsim \nsim I(G_1)\)
Z3 : \(\{a_4, a_5\} \sim \sim C(G_1)\) \(\&\) \(\{a_1, a_2, a_3\} \nsim \nsim I(G_1)\)
Z4 : \(\{a_3, a_5\} \sim \sim C(G_1)\) \(\&\) \(\{a_1, a_2, a_4\} \nsim \nsim I(G_1)\)
Z5 : \(\{a_4\} \sim \sim C(G_1)\) \(\&\) \(\{a_1, a_2, a_3, a_5\} \nsim \nsim I(G_1)\)
A nonsplit graph \(G_1\) has only one split ecards \(G_1-a_1a_2\) if and only if it satisfies one of the following adjacency conditions (1C.7) to (1C.10).
(1C.7:) \(\{a_3, a_4, a_5\}\sim\sim C(G_1),\{a_1, a_2\}\nsim\nsim I(G_1)\) and \(a_3 \sim a_5\).
(1C.8:) \(\{a_3, a_4\}\sim\sim C(G_1)\) and \(\{a_1, a_2, a_5\}\nsim\nsim I(G_1)\)(Figure 3(iv)).
(1C.9:) \(\{a_3, a_5\} \sim \sim C(G_1),\) \(\{a_1, a_2, a_4\} \nsim \nsim I(G_1)\) and \(a_3 \sim a_5\).
(1C.10:) \(\{a_4\} \sim \sim C(G_1),\) \(\{a_1, a_2, a_3, a_5\} \nsim \nsim I(G_1)\) and \(a_3 \nsim a_5\).
Let \(G_2 \in \mathscr{G}\) with
\(T(G_2) = \{a_1, a_2, a_3, a_4, a_5,
a_6\}\),
\(a_1a_2, a_2a_3, a_3a_4, a_1a_4, a_1a_5,
a_3a_5, a_3a_6\in E(G_2)\) and \(a_1a_3, a_2a_4, a_2a_5, a_1a_6, a_2a_6 \notin
E(G_2)\). We shall now construct \(G_2\) such that \(G_2-a_1a_2\) to be split.
\(\underline{a_1a_2 \text{-ecard}}\):
If \(a_1\) was lying in a clique of the maximal edge induced subgraph \(G_2-a_1a_2\), then, since \(a_1a_2, a_1a_3 \notin E(G_2-a_1a_2)\) and \(a_2a_3 \in E(G_2-a_1a_2)\), both \(a_2\) and \(a_3\) would not lie in an independent set of the maximal edge induced subgraph \(G_2-a_1a_2\), giving a contradiction by \(P(C_4)\). Therefore \(a_1\) lies in the independent set partition of the maximal edge induced subgraph \(G_2-a_1a_2\) and \(a_1 \nsim \nsim I(G_2)\). Similarly, \(a_2\) lies in the independent set partition of the maximal edge induced subgraph \(G_2-a_1a_2\) and \(a_2 \nsim \nsim I(G_2)\). Similarly, by \(P(C_4)\), \(a_3, a_4\) and \(a_5\) lie in the clique partition of the maximal edge induced subgraph \(G_2-a_1a_2\) and \(\{a_3,a_4,a_5\} \sim \sim C(G_2).\)
Therefore, one of the following two conditions (W1-W2) must be a necessary condition for maximal edge induced subgraph \(G_2-a_1a_2\) of \(G_2\) to be a split.
W1 : \(\{a_3, a_4, a_5, a_6\} \sim \sim C(G_2)\) \(\&\) \(\{a_1, a_2\} \nsim \nsim I(G_2)\)
W2 : \(\{a_3, a_4, a_5\} \sim \sim C(G_2)\) \(\&\) \(\{a_1, a_2, a_6\} \nsim \nsim I(G_2)\)
A nonsplit graph \(G_2\) has only one split ecards \(G_2-a_1a_2\) if and only if it satisfies one of the following two adjacency conditions (1C.11) to (1C.12).
(1C.11:) \(\{a_3, a_4, a_5,a_6\}\sim\sim C(G_2),\{a_1, a_2\}\nsim\nsim I(G_2),\) \(a_4 \sim \sim \{a_5,a_6\}\) and \(a_5 \sim a_6.\)
(1C.12:) \(\{a_3, a_4, a_5\}\sim\sim C(G_2),\) \(\{a_1, a_2, a_6\}\nsim\nsim I(G_2)\)and \(a_4 \sim a_5\)(Figure 3(v)).
From Subsections 2.1.1 to 2.1.5, we have twelve classes of graphs obtained by applying conditions 1C.1 to 1C.12. Clearly, nonsplit graphs in these twelve classes only have exactly one split ecards. Therefore, we have the following theorem.
Theorem 2.6. A nonsplit graph \(G\) has exactly one split ecard if and only if \(G\) lies in the class of graphs satisfying the conditions 1C.1 to 1C.12.
A nonsplit graph \(G\) with such \(T\) has exactly two split ecards only if \(G\) belongs to any one of the following two families of graphs.
\(\mathscr{F}21:\) Graphs, in \(\mathscr{G},\) containing two induced \(C_4\) with exactly three common vertices (two common edges).
\(\mathscr{F}22:\) Graphs, in \(\mathscr{G},\) containing an induced union of two complete graph on two vertices.
Let \(G_{6} \in \mathscr{G}\) with
\(T(G_6) = \{a_1, a_2, a_3, a_4,
a_5\}\),
\(a_1a_2, a_2a_3, a_3a_4, a_4a_1, a_2a_5,
a_4a_5 \in E(G_6)\) and \(a_1a_3,
a_2a_4, a_3a_5 \notin E(G_6)\). We shall now construct \(G_6\) such that \(G_6-a_2a_3\) and \(G_6-a_3a_4\) are to be split.
\(\underline{a_2a_3 \text{-ecard}}\):
By \(P(C_4)\), \(a_2\) and \(a_3\) lie in an independent set of the maximal edge induced subgraph \(G_6-a_2a_3\) and \(\{a_2, a_3\} \nsim \nsim I(G_6)\) and \(a_1,\) \(a_4\) and \(a_5\) lie in the clique partition of the maximal edge induced subgraph \(G_6-a_2a_3\) and \(\{a_1, a_4, a_5\} \sim \sim C(G_6)\).
Hence a necessary condition for \(G_6-a_2a_3\) to be a split ecard of \(G_6\) is \(\{a_1, a_4, a_5\} \sim \sim C(G_6),\) \(\{a_2, a_3\} \nsim \nsim I(G_6)\) and \(a_1 \sim a_5.\)
\(\underline{a_3a_4 \text{-ecard}}\):
By \(P(C_4)\), \(a_3\) and \(a_4\) lie in an independent set of the maximal edge induced subgraph \(G_6-a_3a_4\) and \(\{a_3, a_4\} \nsim \nsim I(G_6)\) and \(a_1,\) \(a_2\) and \(a_5\) lie in clique of the maximal edge induced subgraph \(G_6-a_3a_4\) and \(\{a_1, a_2, a_5\} \sim \sim C(G_6)\). Hence a necessary condition for \(G_6-a_3a_4\) to be a split ecard of \(G_6\) is \(\{a_1, a_2, a_5\} \sim \sim C(G_6),\) \(\{a_3, a_4\} \nsim \nsim I(G_6)\) and \(a_1 \sim a_5.\)
In the graph \(G_6\) with split ecards \(G_6 – a_2a_3\) and \(G_6 -a_3a_4\), a vertex, that is not in both \(T(G_6)\) and a clique of \(G_6 – a_2a_3,\) does not lie in an independent set of \(G_6 – a_3a_4\) and similarly a vertex, that is not in both \(T(G_6)\) and an independent set of \(G_6 – a_2a_3,\) does not lie in a clique of \(G_6 – a_3a_4\). Therefore, a nonsplit graph \(G_6\) has only two split ecards \(G_6-a_2a_3\) and \(G_6-a_3a_4\) if it satisfies
(2C.1:)\(\{a_1, a_2, a_4, a_5\}\sim\sim C(G_6),\{a_2,a_3,a_4\}\nsim\nsim I(G_6)\) and \(a_1 \sim a_5\)(Figure 4(i)).
Let\(~~\) \(G_{7} \in \mathscr{G}\)\(~~\) with\(~~\) \(T(G_7) = \{a_1, a_2, a_3, a_4\}\),\(~~~~\) \(a_1a_2, a_3a_4 \in E(G_7)\)\(~~~~\) and \(a_1a_3, a_1a_4, a_2a_3, a_2a_4 \notin E(G_7)\). We shall now construct \(G_7\) such that \(G_7-a_1a_2\) and \(G_7-a_3a_4\) are to be split.
\(\underline{a_1a_2 \text{-ecard}}\):
By \(P(2K_2)\), \(a_1\) and \(a_2\) lie in an independent set of the maximal edge induced subgraph \(G_7-a_1a_2\) and \(\{a_1, a_2\} \nsim \nsim I(G_7)\) and either \(a_3\) or \(a_4\) lies in the clique partition of the maximal edge induced subgraph \(G_7-a_1a_2\). Therefore, one of the following three conditions (X1-X3) must be a necessary condition for the maximal edge induced subgraph \(G_7-a_1a_2\) of \(G_7\) to be a split.
X1 : \(\{a_3, a_4\} \sim \sim C(G_7)\) \(\&\) \(\{a_1, a_2\} \nsim \nsim I(G_7)\)
X2 : \(\{a_3\} \sim \sim C(G_7)\) \(\&\) \(\{a_1, a_2, a_4\} \nsim \nsim I(G_7)\)
X3 : \(\{a_4\} \sim \sim C(G_7)\) \(\&\) \(\{a_1, a_2, a_3\} \nsim \nsim I(G_7)\)
\(\underline{a_3a_4 \text{-ecard}}\):
By \(P(2K_2)\), \(a_3\) and \(a_4\) lie in an independent set of the maximal edge induced subgraph \(G_7-a_3a_4\) and \(\{a_3, a_4\} \nsim \nsim I(G_7)\) and either \(a_1\) or \(a_2\) lies in the clique of partition of the maximal edge induced subgraph \(G_7-a_3a_4\). Therefore, one of the following three conditions (Y1-Y3) must be a necessary condition for the maximal edge induced subgraph \(G_7-a_3a_4\) of \(G_7\) to be a split.
Y1 : \(\{a_1, a_2\} \sim \sim C(G_7)\) \(\&\) \(\{a_3, a_4\} \nsim \nsim I(G_7)\)
Y2 : \(\{a_1\} \sim \sim C(G_7)\) \(\&\) \(\{a_2, a_3, a_4\} \nsim \nsim I(G_7)\)
Y3 : \(\{a_2\} \sim \sim C(G_7)\) \(\&\) \(\{a_1, a_3, a_4\} \nsim \nsim I(G_7)\)
Among all conditions (X1-X3) and (Y1-Y3), a nonsplit graph \(G_7\) has only two maximal edge induced split subgraphs \(G_7-a_1a_2\) and \(G_7-a_3a_4\) if it satisfies
(2C.2:) \(\{a_1, a_3\}\sim\sim C(G_7)\) and \(\{a_1,a_2,a_3,a_4\}\nsim\nsim I(G_7)\)(Figure 4(ii)).
From subsections 2.2.1 to 2.2.2, we have two classes of graphs obtained by applying conditions 2C.1 to 2C.2. Clearly, nonsplit graphs in these two classes only have exactly two split ecards. Therefore, we have the following theorem.
Theorem 2.7. A nonsplit graph \(G\) has exactly two maximal edge induced split subgraphs if and only if \(G\) lies in the class of graphs satisfying the conditions 2C.1 and 2C.2.
This case does not arise, because there is no nonsplit graph \(H\) with exactly three split ecards.
A nonsplit graph \(G\) with such \(T\) has exactly four split ecards only if \(G\) belongs to the following family of graphs.
\(\mathscr{F}41:\) graphs in \(\mathscr{G}\) containing an induced cycle on four vertices.
The family \(\mathscr{F}41\):
Let \(G_8 \in \mathscr{G}\) with \(T(G_8) = \{a_1, a_2, a_3, a_4\}\), \(a_1a_2, a_2a_3, a_3a_4, a_4a_1 \in E(G_8)\) and \(a_1a_3, a_2a_4 \notin E(G_8)\). We now construct \(G_8\) such that \(G_8-a_1a_2,\) \(G_8-a_2a_3,\) \(G_8-a_3a_4\) and \(G_8-a_4a_1\) are to be split.
\(\underline{a_1a_2 \text{-ecard}}\):
By \(P(C_4)\), \(a_1\) and \(a_2\) lie in an independent set of the maximal edge induced subgraph \(G_8-a_1a_2\) and \(\{a_1, a_2\} \nsim \nsim I(G_8)\) and \(a_3\) and \(a_4\) lie in the clique partition of the maximal edge induced subgraph \(G_8-a_1a_2\) and \(\{a_3, a_4\} \sim \sim C(G_8)\). Hence a necessary condition for \(G_8-a_1a_2\) to be a split ecard of \(G_8\) is \(\{a_3, a_4\} \sim \sim C(G_8)\) and \(\{a_1, a_2\} \nsim \nsim I(G_8).\)
\(\underline{a_2a_3 \text{-ecard}}\):
By \(P(C_4)\), \(a_2\) and \(a_3\) lie in an independent set of the maximal edge induced subgraph \(G_8-a_2a_3\) and \(\{a_2, a_3\} \nsim \nsim I(G_8)\) and \(a_1\) and \(a_4\) lie in the clique partition of the maximal edge induced subgraph \(G_8-a_2a_3\) and \(\{a_1, a_4\} \sim \sim C(G_8)\). Hence a necessary condition for \(G_8-a_2a_3\) to be a split ecard of \(G_8\) is \(\{a_1, a_4\} \sim \sim C(G_8)\) and \(\{a_2, a_3\} \nsim \nsim I(G_8).\)
\(\underline{a_3a_4 \text{-ecard}}\):
By \(P(C_4)\), \(a_3\) and \(a_4\) lie in an independent set of the maximal edge induced subgraph \(G_8-a_3a_4\) and \(\{a_3, a_4\} \nsim \nsim I(G_8)\) and \(a_1\) and \(a_2\) lie in the clique partition of the maximal edge induced subgraph \(G_8-a_3a_4\) and \(\{a_1, a_2\} \sim \sim C(G_8)\). Hence a necessary condition for \(G_8-a_3a_4\) to be a split ecard of \(G_8\) is \(\{a_1, a_2\} \sim \sim C(G_8)\) and \(\{a_3, a_4\} \nsim \nsim I(G_8).\)
\(\underline{a_4a_1 \text{-ecard}}\):
By \(P(C_4)\), \(a_4\) and \(a_1\) lie in an independent set of the maximal edge induced subgraph \(G_8-a_4a_1\) and \(\{a_4, a_1\} \nsim \nsim I(G_8)\) and \(a_2\) and \(a_3\) lie in the clique partition of the maximal edge induced subgraph \(G_8-a_4a_1\) and \(\{a_2, a_3\} \sim \sim C(G_8)\). Hence a necessary condition for \(G_8-a_4a_1\) to be a split ecard of \(G_8\) is \(\{a_2, a_3\} \sim \sim C(G_8)\) and \(\{a_1, a_4\} \nsim \nsim I(G_8).\)
Therefore, a nonsplit graph \(G_8\) has only four split ecards \(G_8-a_1a_2,\) \(G_8-a_2a_3,\) \(G_8-a_3a_4\) and \(G_8-a_4a_1\) if it satisfies
(4C.1:)\(\{a_1, a_2, a_3, a_4\}\sim\sim C(G_8)\) and \(\{a_1,a_2,a_3,a_4\}\nsim\nsim I(G_8)\)(Figure 4(iii)).
Clearly nonsplit graphs in this class only have exactly four split ecards. Therefore, we have the following theorem.
Theorem 2.8. A nonsplit graph \(G\) has exactly four split ecards if and only if \(G\) lies in the class of graphs satisfying the conditions 4C.1.
In this paper, we have listed
(i) twelve families of nonsplit graphs having exactly one split ecard;
(ii) two families of split graphs having exactly two split ecards; and
(iii) only one family of nonsplit graphs having exactly four split ecards.
Using these fifteen classes of nonsplit graphs, we can check whether any given nonsplit graph has a split ecard or not. This may give us inference to find the edge reconstruction number of nonsplit graphs.
This study was funded by National Board for Higher Mathematics(NBHM), Government of India (grant number: 02011/14/2022/NBHM(R.P)/\(\text{R}\&\text{D}\) II). S. Monikandan has received research grants from National Board for Higher Mathematics(NBHM), Government of India. V. Manikandan declares that he has no conflict of interest.