Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 8s (2025) 888 https://internationalpubls.com Degree Associated Reconstruction Number of Split Graphs with Some Biregular Independent Set A. Anu Assistant Professor Department of Mathematics Vivekananda College, Agasteeswaram Kanyakumari, Tamil Nadu, INDIA esa.anu1188@gmail.com Article History: Received: 08-11-2024 Revised:23-12-2024 Accepted:06-01-2025 Abstract: A vertex-deleted subgraph of a graph G with which the degree of the deleted vertex is given is called a degree associated card of G. The degree associated reconstruction number (or drn) of a graph G is the size of the smallest collection of the degree associated cards of G that uniquely determines G. A split graph G is a graph in which the vertices can be partitioned into an independent set and a clique. We prove that the drn is 1 or 2 for all split graphs G of order at least seven in which all the vertices in the independent set have degrees r and s whose distinct degrees differ by at least two. Keywords: Isomorphism, Reconstruction, Reconstruction number, Split graph. 1 Introduction All graphs considered in this paper are finite, simple and undirected. We shall mostly follow the graph theoretic terminology of [8]. A vertex-deleted subgraph or card G − v of a graph (digraph) G is the unlabelled graph (digraph) obtained from G by deleting the vertex v and all edges (arcs) incident with v. The deck of a graph (digraph) G is its collection of cards. Following the formulation in [2], a graph (digraph) G is reconstructible if it can be uniquely determined from its deck. The well-known Reconstruction Conjecture (RC) due Kelly [13] and Ulam [26] asserts that every graph with at least three vertices is reconstructible. The conjecture has been proved for many special classes, and many properties of G may be deduced from its deck. Nevertheless, the full conjecture remains open. Surveys of results on the RC and related problems include [7, 17]. Harary and Plantholt [10] defined the reconstruction number of a graph G, denoted by rn(G), to be the minimum number of cards which can only belong to the deck of G and not to the deck of any other graph H, H  G, these cards thus uniquely identifying G. Reconstruction numbers are known for only few classes of graphs [5]. An extension of the RC to digraphs is the Digraph Reconstruction Conjecture (DRC), proposed by Harary [9], which asserts that every digraph with at least seven vertices is reconstructible. The DRC was disproved by Stockmeyer [25] by exhibiting several infinite families of counter-examples and this made people doubt the RC itself. To overcome this, Ramachandran [21] introduced degree associated reconstruction for digraphs and proposed a new conjecture in 1981. It was proved [21] that the digraphs in all these counterexamples to the DRC obey the new conjecture, thereby protecting the RC from the threat posed by these digraph counterexamples. The ordered triple (a, b, c) where a, b and c are respectively the number of unpaired out arcs, unpaired in arcs and symmetric pair of arcs incident with v in a digraph D is called the degree triple of v. The degree associated card or dacard of a digraph (graph) is a pair (d, C) consisting of a card C and the degree triple (degree) d of the deleted vertex. The dadeck of a digraph is the multiset of all its dacards. A digraph is said to be N-reconstructible Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 8s (2025) 889 https://internationalpubls.com if it can be uniquely determined from its dadeck. The new digraph reconstruction conjecture [21] (NDRC) asserts that all digraphs are N-reconstructible. Ramachandran [22, 23] then studied the degree associated reconstruction number of graphs and digraphs in 2000. The degree (degree triple) associated reconstruction number of a graph (digraph) D is the size of the smallest collection of dacards of D that uniquely determines D. Articles [2], [3], [4], [6] and [15] are recent papers on the degree associated reconstruction number. A split graph G is a graph in which the vertices can be partitioned into an independent set (say X (G) or simply X) and a clique (say Y (G) or simply Y). Here we use G, X and Y in the sense of this definition. S. Monikandan and N. Kalaimathi [11] have shown that all split graphs G with regular independent set have drn (G) ≤ 3. In this paper, we prove that drn(G) = 1 or 2 for all split graphs G of order at least seven in which all the vertices in X have only r and s degrees in G. 2 Drn of Split Graphs In a graph G of order n, a vertex with degree d is called a d -vertex. The degree of a vertex v in G is denoted by degG v or simply deg v. The neighbourhood of a vertex v in G, written NG (v) or simply N (v), is the set of vertices adjacent to v in G. The next theorem, due to Barrus and West [6], characterizes all graphs G with drn (G) = 1. Theorem 1. The dacard (C, d) belongs to the dadeck of only one graph (up to isomorphism) if and only if one of the following holds: (1) d = 0 or d = |V (C)| ; (2) d = 1 or d = |V (C) − 1| , and C is vertex-transitive; (3) C is complete or edgeless. Ramachandran [22] has shown that all split graphs G on at most 6 vertices have drn (G) = 1, 2 or 3. So, we assume that all split graphs G consider hereafter have order at least seven and that the independent set is biregular in G. Let |X| = m1 > 0 and |Y | = m2 > 0. Then we have 0 < r < s ≤ m2. Let Yi denote the set of vertices in Y that are adjacent to exactly i vertices in X for i = 0, 1, ... m1. Then, in G, the degree of a vertex v ∈ Yi is m2 − 1 + i for i = 0, 1, ... m1. Let k1, k2, ... kt be integers, where 0 ≤ k1 < k2 < ... < kt ≤ m1, such that Yki ≠ ϕ for all i = 1, 2, ..., t. Thus Y can be written as 1 t i=U ikY . Theorem 2. If G is a split graph with at least one vertex of X is adjacent to all the vertices of Y, then drn (G) = 2. Proof. Let us take X = {x1, x2... x 1m }. Case 1. deg (xs) = s, s ≠ 1 to m1 − 1. Clearly xs = x 1m . In this case, the graph are isomorphic to a split graph in which the vertices can be partition into an independent set and a clique such that all the vertices in the independent set have equal degree, then drn (G) = 2 [11]. Case 2. deg (xs) = deg (xi) = s, for some i = 1 to m1 − 1. Let us take y ∈ tkY . Consider the two dacards ( tk , G − y) and (r, G − xr). It is clear that the dacard G − xr has two partite set such that one partite set is clique and other partite set has degree r or s in which m(≥ 2 say) vertices of degree s. To get an extension H ( tk , G−y), add a new vertex v to the dacard G−y and join it Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 8s (2025) 890 https://internationalpubls.com with precisely tk vertices. Clearly G − y contains exactly one partite set (say Z1 ) having a clique. If v were joined to all the vertices in Z1 and all the vertices of degrees r − 1 and s − 1, then the resulting extension H would be isomorphic to G. Otherwise, in every extension H ( tk , G − y) the newly added vertex v is joined to at least one vertex of degree r or s. But then any r -vertex deleted dacard of H contains an independent set having a vertex of degree r + 1 or s + 1 or at least m + 1 vertices of degree s or two adjacent vertices and so it is not isomorphic to G − xr. Thus no graph other than G contains both the two dacards ( tk , G − y) and (r, G − xr) in its dadeck and hence drn (G) = 2. Theorem 3. If G is a split graph with deg yi+1 = deg yi + 1 for some i, then drn (G) = 2. Proof. Let us assume that Yp1 < Yp2 < ... < kpY are all satisfies our hypothesis. Here we use the two dacards (d ( kpy ), G − kpy ) and (r, G − xr) where kpy ∈ kpY . In G− kpy , exactly one partite set contains x1, x2, x3, x4 vertices of degree r− 1, r, s− 1, s respectively and other partite set form a clique. In G − xr, exactly one independent partite set is (r, s) -regular. Now we consider the extension of H (d ( kpy ), G − kpy ), add a new vertex v to the dacard G − kpy and join it with precisely d ( kpy ) vertices. Clearly G − kpy contains exactly one partite set (say Z1 ) having a clique. If v were joined to all the vertices in Z1 and all the vertices of degrees r − 1 and s − 1, then the resulting extension H would be isomorphic to G. Otherwise, in every extension H (d ( kpy ), G− kpy ) the newly added vertex v is joined to at least one vertex of degree r or s. But then any r -vertex deleted dacard of H contains an independent set having a vertex of degree r + 1 or s + 1 and so it is not isomorphic to G−xr. Thus no graph other than G contains both the two dacards (d ( kpy ), G− kpy ) and (r, G−xr) in its dadeck and hence drn (G) = 2. Theorem 4. If G is a split graph with at least one vertex of X is not adjacent to exactly one vertex of Y, then drn (G) = 2. Proof. The graph G is clearly connected. Let z be the vertex adjacent to all the vertices except one vertex (say y1) in the other partite set Y of G. Clearly deg z = m2 − 1. Let us take deg y1 = n1. Consider the two dacards (r, G − xr) and (n1, G − y1). It is clear that the dacard G − y1 has m (≥ 1 say) vertices of degree m2 − 1 and degree of a vertex y ∈ Yi is m2 − 1 + i − 1 for i = 0 to m1. To get an extension H(r, G − xr), add a new vertex v to the dacard G − xr and join it with precisely r vertices. Here, G − xr contains at least one (m2 − 1) -vertex, say z1 and a vertex, say z2 of degree m2 − 1 + k (k is maximum) which is non adjacent to z1 but adjacent to all the neighbours of z1. The vertex z2 and all the neighbours of z1 form a clique such that exactly r vertices of degree m2 − 1 + i − 1 for i = 1 to m1. If v were joined to z2 and N (z1), then the resulting extension H would be isomorphic to G. Otherwise, in every extension H, the newly added vertex v is joined to at least one vertex not in N (z1) and z2 But then any n1 -vertex deleted dacard of H contains at most m− 1 vertices of degree m2 − 1 or degree of at least one vertex y ∈ Yi is m2 + i− 3 for some i. Thus no graph other than G contains both the two dacards (r, G − xr) and (n1, G − y1) in its dadeck and hence drn (G) = 2. Theorem 5. If G is a split graph with at least one vertex of Y is not adjacent to all the vertices of X, then drn (G) = 2. Proof. Let y be a vertex non adjacent to the vertices of X and x be a vertex of degree s. Clearly deg y = m2 − 1 and s ≤ m2 − 2. Case 1. s  m2 − 2. Here we use the two dacards (s, G−x s) and (m2 − 1, G−y). In G−y, exactly one partite set is (r, s) -regular and Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 8s (2025) 891 https://internationalpubls.com degree of all vertices y ∈ Yi of other partite set is m2 − 1 + i − 1 for i = 0 to m1. In the extension H(s, G − xs) if the newly added vertex v were joined to all the vertices of degree m2 − 1+ i− 1 for i = 1 to m1, then the resulting extension H would be isomorphic to G. Otherwise, at least two vertices of degree r or s are adjacent or degree of at least one vertex y ∈ Yi is m2 + i − 3 for some i. Case 2. s = m2 − 2. Here we use the two dacards (r, G−x r) and (m2 − 1, G−y). In G−y, exactly one partite set is (r, s) -regular and degree of all vertices y ∈ Yi of other partite set is m2 − 1 + i − 1 for i = 0 to m1. In the extension H(r, G − xr) if the newly added vertex v were joined to all the vertices of degree m2 − 1+ i− 1 for i = 1 to m1, then the resulting extension H would be isomorphic to G. Otherwise, at least two vertices of degree r or s are adjacent or degree of at least one vertex y ∈ Yi is m2 + i − 3 for some i. Thus no graph other than G contains both the two dacards (r, G − xr) and (m2 − 1, G − y) in its dadeck and hence drn (G) = 2. Theorem 6. If G is a split graph with s  r + 1, then drn (G) = 2. Proof. We can assume that deg iky ≥ m2 ∀i and 1 ≤ r < s ≤ m2 −2 because every vertex of X is not adjacent to at least two vertices of Y and every vertex of Y is adjacent to at least one vertex of X. Consider the two dacards (d(y), G−y) and (r, G−xr). It is clear that the dacard G−x r has two partite sets such that one partite set is clique and every vertex of other partite set has degree r or s. Now we consider the extension of (d(y), G − y). If the newly added vertex v were joined to all the vertices of degrees r − 1 and s − 1 and also joined to all the vertices of a clique then the resulting extension H would be isomorphic to G. Otherwise, any r - vertex deleted dacard of H contains at least one vertex of degree r + 1 or s + 1. Hence such a dacard is not isomorphic to G − xr. Therefore, no graph other than G contains both these two dacards in its dadeck, we have drn (G) = 2. 3 Conclusion For graphs with at least three vertices, knowing the degree of the deleted vertex is equivalent to knowing the total number of edges. A simple counting argument computes the size of the graph when its entire deck is known. So the dadeck gives the same information as the deck. However, the counting argument requires the entire deck, so an individual dacard gives more information than the corresponding card. In the above sections, we have proved that the drn is 1 or 2 for a split graph G of degree at least seven with biregular independent set whose degrees differ by two. There is a hope to complete a proof of drn (G) ≤ 3 for all split graphs G. References [1] A. Anu and S. Monikandan, Nearly all biregular graphs have degree associated edge reconstruction number at most three, Ars Combinatoria, 147, 263-280 (2020). [2] P. Anusha Devi and S. Monikandan, Degree associated reconstruction number of graphs with regular pruned graph, Ars Combinatoria 134, 29-41, (2017). [3] P. Anusha Devi and S. Monikandan, Degree associated reconstruction numbers of total graph, Contribution to Discrete Mathematics 12(2), 77-90, (2017). [4] A. Anu and S. Monikandan, Degree associated reconstruction number of biregular bipartite graphs with degree differ by at least two, proceedings of the ICTCDM, LNCS 10398,Springer-Verlag, Berlin, 1-9, 2017. [5] K. J. Asciak, M.A. Francalanza, J. Lauri and W. Myrvold, A survey of some open questions in reconstruction numbers, Ars Combinatoria 97, 443-456 (2010). [6] M.D. Barrus and D.B. West, Degree-associated reconstruction number of graphs, Discrete Math. 310, 2600-2612 (2010). Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 8s (2025) 892 https://internationalpubls.com [7] J.A. Bondy, A graph reconstructors manual, in Surveys in Combinatorics (Proc. 13th British Combin. Conf.) London Math. Soc. Lecture Note Ser. 166, 221252(1991). [8] F. Harary, Graph Theory, Addison Wesley, Mass. (1969). [9] F. Harary, On the reconstruction of a graph from a collection of subgraphs, in ”Theory of graphs and its applications”, (M. Fieldler, Ed.), Academic Press, New York, 47- 52 (1964). [10] F. Harary and M. Plantholt, The graph reconstruction number, J. Graph Theory, Vol. 9, 451-454 (1985). [11] N. Kalai Mathi and S. Monikandan, Degree associated reconstruction number of split graphs with regular independent set, proceedings of the ICTCDM, LNCS 10398, Springer-Verlag, Berlin, 106-112, 2017. [12] S. Monikandan and N. Kalai Mathi, Degree associated edge reconstruction number of split graphs with regular independent set is one or two, Journal of Combinatorics and Number Theory 10(1), 63-73, (2019). [13] P. J. Kelly, On isometric transformations, PhD Thesis, University of Wisconsin Madison, (1942). [14] W.L. Kocay, Partial automorphisms and the reconstruction conjecture, J. Austral. Math. Soc. (Ser A) 37,317336 (1984). [15] M. Ma, H. Shi, H. Spinoza and D. B. West, Degree-associated reconstruction parameters of complete multipartite graphs and their complements, Taiwanese J. Math., Vol. 19, No. 4, 1271-1284 (2015). [16] M. Ma, H. Shi and D. B. West, The adversary degree associated reconstruction number of double brooms, J. Discrete Algorithms 33,1̃50159(̃2015). [17] B. Manvel, Reconstruction of graphs - Progress and prospects, Congr. Numer. 63, 177- 187 (1988). [18] R. Molina, The edge reconstruction number of a disconnected graph, J. Graph Theory 19 (3), 375-384 (1995). [19] S. Monikandan and S. Sundar Raj, Degree associated edge reconstruction number, in: Combinatorial Algorithms, in: Lect. Notes Comput. Sci., vol. 7643, Springer-Verlag, Berlin, 100-109 (2012). [20] S. Monikandan, P. Anusha Devi and S. Sundar Raj, Degree associated edge reconstruction number of graphs, J. Discrete Algorithms 23, 35-41 (2013). [21] S. Ramachandran, On a new digraph reconstruction conjecture, J. Combin. Theory Ser. B 31, 143-149 (1981). [22] S. Ramachandran, Degree associated reconstruction number of graphs and digraphs, Mano. Int. J. Math. Scis. 1, 41-53 (2000). [23] S. Ramachandran, Reconstruction number for Ulam’s conjecture. Ars Combin. 78,2̃89296(̃2006). [24] S. Ramachandran and S. Monikandan, Graphs with n − 3 isomorphic vertex-deleted subgraphs, and their reconstructibility, Utilitas Mathematica 75, 225-248 (2008). [25] P. K. Stockmeyer, The falsity of the reconstruction conjecture for tournaments, J. Graph Theory 1, 19-25 (1977). [26] S. M. Ulam, A collection of mathematical problems, Interscience Tracts in Pure and Applied Mathematics 8, (Interscience Publishers, 1960).