We study completely independent spanning trees (CIST), i.e. , trees that are both edge-disjoint and internally vertex-disjoint, in split graphs. We establish a correspondence between the existence of CIST in a split graph and some types of hypergraph colorings (panchromatic and bipanchromatic colorings) of its associated hypergraph, allowing us to obtain lower and upper bounds on the number of CIST. Using these relations, we prove that the problem of the existence of two CIST in a split graph is NP-complete. Finally, we formulate a conjecture on the bipanchromatic number of a hypergraph related to the results obtained for the number of CIST.

Identifying important nodes in networked systems is crucial for network analysis and many other applications. Different metrics have been used to assess the node importance within a network, generally as a property to be fulfilled by the node deletion. In this work, we consider as important nodes those whose deletion partitions the network into connected components of a given size. Given the graph G representing the network, we look for the smallest subset of nodes whose removal partition G into components of at most κ nodes, where κ is a given bound. This problem has already been shown to be NP-complete even when restricted to particular classes of graphs, which is the case for general chordal graphs. In this paper, we develop a polynomial-time algorithm to solve it on chordal graphs with maximum node degree Δ = 3. The proposed algorithm returns an exact solution in O(n2) for a graph G of n nodes.

In the context of disaster management, Software-Defined Internet of Things (SD-IoT) networks playa crucial role by utilizing critical real-time data essential for addressing disasters. However, managing these networks becomes more complicated due to the heterogeneity of traffic and the load generated by each switch when transmitting information to the controller. This heterogeneity makes the controller placement issue critical. To address this challenge, we propose an opti-mization method called HTF -CP (Heterogeneous Traffic Flow-Based Controller Placement), based on the well-known Lidy+ method, which optimizes the placement of controllers while managing heterogeneous traffic in the network. We demonstrate the approach's efficiency through simulations on datasets from the Internet Topology Zoo and OS3E. The proposed method is evaluated in terms of maximum latency, average latency, and load rate. The experimental results show that our HTF -CP method provides better performance compared to Lidy+ and the random method, where the controller is selected randomly.

Protecting network applications against malicious behaviors is one of the main concerns when designing network applications. A secured application must take into account any network weakness that an attacker may exploit. One of the major weaknesses is network disconnectivity. A network becomes disconnected by removing nodes/links. This nodes/links are those those that maintain the whole network connectivity, and known as the critical elements. In this paper, we consider the problem of finding critical nodes in networks, which is a good way to assess network vulnerability. This problem consists in finding the smallest subset of nodes, in a given network, the deletion of which partitions it into connected components of the minimum cardinality. We investigate the problem complexity on the class of networks modeled by split graphs, where we show that it remains NP-hard, and hence heuristic approaches are well-suitable for finding near optimal solutions.