Search

Given a finite group G, the coprime graph of G, denoted by Î(G), is defined as an undirected graph with the vertex set G, and for distinct x, y â G, x is adjacent to y if and only if (o(x), o(y)) = 1, where o(x) and o(y) are the orders of x and y, respectively. This paper classifies the finite groups with split, threshold and chordal coprime graphs, as well as gives a characterization of the finite groups whose coprime graph is a cograph. As some applications, the paper classifies the finite groups G such that Î(G) is a cograph if G is a nilpotent group, a dihedral group, a generalized quaternion group, a symmetric group, an alternating group, or a sporadic simple group.

Consider a graph G = (V , E) and a function f : V → { 0 , 1 , 2 }. A vertex u with f (u) = 0 is defined as undefended by f if it lacks adjacency to any vertex with a positive f -value. The function f is said to be a weak Roman dominating function (WRD function) if, for every vertex u with f (u) = 0 , there exists a neighbor v of u with f (v) > 0 and a new function f ′ : V → { 0 , 1 , 2 } defined in the following way: f ′ (u) = 1 , f ′ (v) = f (v) − 1 , and f ′ (w) = f (w) , for all vertices w in V ∖ { u , v } ; so that no vertices are undefended by f ′. The total weight of f is equal to ∑ v ∈ V f (v) , and is denoted as w (f). The Weak Roman domination number denoted by γ r (G) , represents m i n { w (f) | f is a WRD function of G }. For a given graph G , the problem of finding a WRD function of weight γ r (G) is defined as the Minimum Weak Roman domination problem. The problem is already known to be NP-hard for bipartite and chordal graphs. In this paper, we further study the algorithmic complexity of the problem. We prove the NP-hardness of the problem for star convex bipartite graphs and comb convex bipartite graphs, which are subclasses of bipartite graphs. In addition, we show that for the bounded degree star convex bipartite graphs, the problem is efficiently solvable. We also prove the NP-hardness of the problem for split graphs, a subclass of chordal graphs. On the positive side, we present a polynomial-time algorithm to solve the problem for P 4 -sparse graphs. Further, we have presented some approximation results. [ABSTRACT FROM AUTHOR]

Let r ≥ 3 be an integer. A graph G is K 1 , r - free if G does not have an induced subgraph isomorphic to K 1 , r , and is a split graph if the vertex set of G can be partitioned into a clique and a stable set. It has been conjectured that for any r ≥ 3 , every (r − 1) -connected K 1 , r -free split graph is hamiltonian and every r -connected K 1 , r -free split graph is Hamilton-connected. These conjectures have been verified when r ∈ { 3 , 4 }. A graph G is spanning s -connected if for any pair of distinct vertices u , v ∈ V (G) and for all integers k with 0 ≤ k ≤ s , there exists a spanning subgraph of G consisting of k -internally disjoint (u , v) -paths. Thus G is spanning 1-connected implies that G is Hamilton-connected, and so is hamiltonian. We prove that for integers r and s with r ∈ { 3 , 4 } and s ≥ 3 , each of the following holds for a K 1 , r -free split graph G : (i) When r = 3 , G is s -connected if and only if G is spanning s -connected. (ii) When r = 4 , if G is 4-connected, then G is spanning 3-connected. (iii) If G is (r + 2 s − 5) -connected, then G is spanning s -connected. These results (i) and (ii) extend former results on Hamilton-connectedness of 3-connected K 1 , r -free split graphs in Liu et al. (2023). [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph where V and E are the vertex and edge sets, respectively. For two disjoint subsets A and B of V , we say A dominates B if every vertex of B is adjacent to at least one vertex of A. A vertex partition π = { V 1 , V 2 , ... , V k } of G is called a transitive partition of size k if V i dominates V j for all 1 ≤ i < j ≤ k. In this article, we study a variation of transitive partition, namely 2- transitive partition. For two disjoint subsets A and B of V , we say A 2- dominates B if every vertex of B is adjacent to at least two vertices of A. A vertex partition π = { V 1 , V 2 , ... , V k } of G is called a 2- transitive partition of size k if V i 2 -dominates V j for all 1 ≤ i < j ≤ k. The Maximum 2- Transitivity Problem is to find a 2 -transitive partition of a given graph with the maximum number of parts. We show that the decision version of this problem is NP-complete for chordal and bipartite graphs. On the positive side, we design three linear-time algorithms for solving Maximum 2- Transitivity Problem in trees, split, and bipartite chain graphs. [ABSTRACT FROM AUTHOR]

A vertex partition π = {V1,V2,…,Vk} of G is called a transitive partition of size k if Vi dominates Vj for all 1 ≤ i < j ≤ k. For two disjoint subsets A and B of V, we say A strongly dominates B if for every vertex y ∈ B, there exists a vertex x ∈ A, such that xy ∈ E and degG(x) ≥degG(y). A vertex partition π = {V1,V2,…,Vk} of G is called a strong transitive partition of size k if Vi strongly dominates Vj for all 1 ≤ i < j ≤ k. The maximum strong transitivity problem involves finding a strong transitive partition of a given graph with the maximum number of parts. In this paper, we initiate the study of this variation of transitive partition from an algorithmic point of view. We show that the decision version of this problem is NP-complete for chordal graphs. On the positive side, we prove that this problem can be solved in linear time for trees and split graphs. [ABSTRACT FROM AUTHOR]

Given a graph G with a terminal set R ⊆ V (G) , the Steiner tree problem (STREE) asks for a set S ⊆ V (G) \ R such that the graph induced on S ∪ R is connected. A split graph is a graph which can be partitioned into a clique and an independent set. It is known that STREE is NP-complete on split graphs White et al. (Networks 15(1):109–124, 1985). To strengthen this result, we introduce convex ordering on one of the partitions (clique or independent set), and prove that STREE is polynomial-time solvable for tree-convex split graphs with convexity on clique (K), whereas STREE is NP-complete on tree-convex split graphs with convexity on independent set (I). We further strengthen our NP-complete result by establishing a dichotomy which says that for unary-tree-convex split graphs (path-convex split graphs), STREE is polynomial-time solvable, and NP-complete for binary-tree-convex split graphs (comb-convex split graphs). We also show that STREE is polynomial-time solvable for triad-convex split graphs with convexity on I, and circular-convex split graphs. Further, we show that STREE can be used as a framework for the dominating set problem (DS) on split graphs, and hence the classical complexity (P vs NPC) of STREE and DS is the same for all these subclasses of split graphs. Finally, from the parameterized perspective with solution size being the parameter, we show that the Steiner tree problem on split graphs is W[2]-hard, whereas when the parameter is treewidth, we show that the problem is fixed-parameter tractable, and if the parameter is the solution size and the maximum degree of I (d), then we show that the Steiner tree problem on split graphs has a kernel of size at most (2 d - 1) k d - 1 + k , k = | S | . [ABSTRACT FROM AUTHOR]

We study binary action network games with strategic complementarities. An agent acts if the aggregate social influence of her friends exceeds a transfer levied on the agent by a principal. The principal seeks to maximize her revenue while inducing everyone to act in a unique equilibrium. We characterize optimal transfers showing that agents who are more popular than their friends receive preferential treatment. Our main result is that under mild conditions complete core‐periphery networks deliver the highest revenue to the principal. Furthermore, we show that the revenue is higher in networks where links are allocated unequally across agents. Hence, the principal benefits from creating "influentials" by linking well‐connected hubs to less popular periphery. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) and an integer k, the Minimum Membership Dominating Set (MMDS) problem seeks to find a dominating set S ⊆ V of G such that for each v ∈ V , | N [ v ] ∩ S | is at most k. We investigate the parameterized complexity of the problem and obtain the following results for the MMDS problem. First, we show that the MMDS problem is NP-hard even on planar bipartite graphs. Next, we show that the MMDS problem is W[1]-hard for the parameter pathwidth (and thus, for treewidth) of the input graph. Then, for split graphs, we show that the MMDS problem is W[2]-hard for the parameter k. Further, we complement the pathwidth lower bound by an FPT algorithm when parameterized by the vertex cover number of input graph. In particular, we design a 2 O (v c) | V | O (1) time algorithm for the MMDS problem where vc is the vertex cover number of the input graph. Finally, we show that the running time lower bound based on ETH is tight for the vertex cover parameter. [ABSTRACT FROM AUTHOR]

The biclique partition number (bp) of a graph G is referred to as the least number of complete bipartite (biclique) subgraphs that are required to cover the edges of the graph exactly once. In this paper, we show that the biclique partition number of a co-chordal (complementary graph of chordal) graph G = (V , E) is less than the number of maximal cliques (mc) of its complementary graph: A chordal graph G c = (V , E c). We first provide a general framework of the "divide and conquer" heuristic of finding minimum biclique partitions of co-chordal graphs based on clique trees. Furthermore, a heuristic of complexity O (| V | (| V | + | E c |)) is proposed by applying a lexicographic breadth-first search to find structures called moplexes. Either heuristic gives us a biclique partition of G with a size of mc (G c) − 1. In addition, we prove that both of our heuristics can solve the minimum biclique partition problem on G exactly if its complement G c is chordal and clique vertex irreducible. We also show that mc (G c) − 2 ≤ bp (G) ≤ mc (G c) − 1 if G is a split graph. [ABSTRACT FROM AUTHOR]

Let t be a positive real number. A graph is called t-tough if the removal of any vertex set S that disconnects the graph leaves at most |S|/t components, and all graphs are considered 0-tough. The toughness of a graph is the largest t for which the graph is t-tough, whereby the toughness of complete graphs is defined as infinity. A graph is minimally t-tough if the toughness of the graph is t, and the deletion of any edge from the graph decreases the toughness. In this paper, we investigate the minimum degree and the recognizability of minimally t-tough graphs in the classes of chordal graphs, split graphs, claw-free graphs, and 2K2-free graphs. [ABSTRACT FROM AUTHOR]

Computer networks are prone to targeted attacks and random failures. Robustness is a measure of an ability of a network to continue functioning when part of the network is either naturally damaged or targeted for attack. The study of network robustness is a critical tool in the characterization and understanding of complex interconnected systems. There are several proposed graph metrics that predicates network resilience against such attacks. Isolated rupture degree is a novel graph-theoretic concept defined as a measure of network vulnerability. Isolated rupture degree is argued as an appropriate measure for modelling the robustness of network topologies in the face of possible node destruction. In this paper, the relationships between isolated rupture degree and some other graph parameters such as connectivity, covering number, minimum vertex degree are established. The isolated rupture degrees of 2 K 2 -free graphs, middle graphs, corona graphs of a middle graph and a complete graph K 2 on two vertices are evaluated, then compared and the more stable graph types are reported. A sharp upper bound for the isolated rupture degree of middle graphs is established. [ABSTRACT FROM AUTHOR]

A connection tree of a graph G for a terminal set W is a tree subgraph T of G such that leaves(T) ⊆ W ⊆ V(T). A non-terminal vertex is called linker if its degree in T is exactly 2, and it is called router if its degree in T is at least 3. The Terminal connection problem (TCP) asks whether G admits a connection tree for W with at most ℓ linkers and at most r routers, while the Steiner tree problem asks whether G admits a connection tree for W with at most k non-terminal vertices. We prove that, if r ≥ 1 is fixed, then TCP is polynomial-time solvable when restricted to split graphs. This result separates the complexity of TCP from the complexity of Steiner tree, which is known to be NP-complete on split graphs. Additionally, we prove that TCP is NP-complete on strongly chordal graphs, even if r ≥ 0 is fixed, whereas Steiner tree is known to be polynomial-time solvable. We also prove that, when parameterized by clique-width, TCP is W[1]-hard, whereas STeiner tree is known to be in FPT. On the other hand, agreeing with the complexity of Steiner tree, we prove that TCP is linear-time solvable when restricted to cographs (i.e. graphs of clique-width 2). Finally, we prove that, even if either ℓ ≥ 0 or r ≥ 0 is fixed, TCP remains NP-complete on graphs of maximum degree 3. [ABSTRACT FROM AUTHOR]

The biclique graph is the intersection graph of the bicliques of a graph. Its recognition problem is still open. In this paper we study the problem restricted to the class of split graphs. We define a class called nested separable split graphs and solve the recognition problem of biclique graphs of a subclass of the mentioned class. For that, we give a polynomial time algorithm with positive certificate. We also characterize nested split graphs and study properties of biclique graphs of split graphs. For example, we show that they are Hamiltonian. We also present a complexity result for recognizing graphs such that their biclique graphs are complete graphs, that is, we prove that the problem of recognizing biclique-complete graphs in co- NP -complete. [ABSTRACT FROM AUTHOR]

An interval graph is the intersection graph of a family F of intervals on the real line. An interval order is a partial order (F , ≺) , where F is a family of intervals on the real line, such that for all I 1 , I 2 ∈ F , I 1 ≺ I 2 if and only if I 1 lies entirely to the left of I 2. In both cases, the family F is called a model of the graph (order). The interval count of a given graph (resp. order) is the smallest number of interval lengths needed in any model of this graph (resp. order). The first problem we consider is related to the classes of graphs and orders which can be represented with two interval lengths a and b , with respect to the inclusion hierarchy among such classes for variables a , b. The second problem is an extremal problem which consists of determining the smallest graph or order which has interval count at least k. In particular, we study a conjecture by Fishburn on this extremal problem, verifying its validity when such a conjecture is constrained to the classes of trivially perfect orders and split orders. [ABSTRACT FROM AUTHOR]

A graph is circle if its vertices are in correspondence with a family of chords in a circle in such a way that every two distinct vertices are adjacent if and only if the corresponding chords have nonempty intersection. Even though there are diverse characterizations of circle graphs, a structural characterization by minimal forbidden induced subgraphs for the entire class of circle graphs is not known, not even restricted to split graphs (which are the graphs whose vertex set can be partitioned into a clique and a stable set). In this work, we give a characterization by minimal forbidden induced subgraphs of circle graphs, restricted to split graphs. [ABSTRACT FROM AUTHOR]

Let G be a connected graph with vertex set V (G). The distance, d G (u , v) , between vertices u and v in G is defined as the length of a shortest path between u and v in G. The distance matrix of G is the matrix D (G) = (d G (u , v)) u , v ∈ V (G). The second largest distance eigenvalue of G is the second largest one in the spectrum of D (G). We show that any connected graph with the second largest distance eigenvalue less than − 1 2 is chordal, and characterize those bicyclic graphs and split graphs with the second largest distance eigenvalue less than − 1 2. [ABSTRACT FROM AUTHOR]

In the minimum degree vertex deletion problem, we are given a graph, a distinguished vertex in the graph, and an integer κ, and the question is whether we can delete at most κ vertices from the graph so that the distinguished vertex has the unique minimum degree. The maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum degree. It is known that both problems are NP-hard and fixed-parameter intractable with respect to some natural parameters. In this paper, we study the (parameterized) complexity of these two problems restricted to split graphs, p-degenerate graphs, and planar graphs. Our study provides a comprehensive complexity landscape of the two problems restricted to these special graphs. [ABSTRACT FROM AUTHOR]

The spanning trees of a graph constructed by the graph searches BFS and DFS are some of the most elementary structures in algorithmic graph theory. BFS-trees are first-in trees, i.e., every vertex is connected to its first visited neighbor. DFS-trees are last-in trees, i.e., every vertex is connected to its most recently visited neighbor. It is known since the 1980s that the problem of deciding whether a given spanning tree of a graph is a BFS-tree or a DFS-tree can be solved in linear time. Here, we will show that swapping the search-tree paradigms between these searches makes the problem hard, i.e., it is NP -complete to decide whether a spanning tree of a graph is a first-in-tree of a DFS or a last-in-tree of a BFS. To the best of our knowledge the latter result is the first hardness result for the recognition of last-in-trees for some graph search. Additionally, we study the complexity of both problems on split graphs. • Hardness of the recognition of last-in trees of BFS. • Hardness of the recognition of first-in trees of DFS. • Linear-time algorithm for the recognition of first-in trees of DFS on split graphs. • Better understanding of the last-in trees of generic search. [ABSTRACT FROM AUTHOR]

In a (parameterized) graph edge modification problem, we are given a graph G, an integer k and a (usually well-structured) class G of graphs, and asked whether it is possible to transform G into a graph G ′ ∈ G by adding and/or removing at most k edges. Parameterized graph edge modification problems received considerable attention in the last decades. In this paper, we focus on finding small kernels for edge modification problems. One of the most studied problems is the Cluster Editing problem, in which the goal is to partition the vertex set into a disjoint union of cliques. Even if a 2k-vertex kernel exists for Cluster Editing, this kernel does not reduce the size of the instance in most cases. Therefore, we explore the question of whether linear kernels are a theoretical limit in edge modification problems, in particular when the target graph class is very structured (such as a partition into cliques for instance). We prove, as far as we know, the first sublinear kernel for an edge modification problem. Namely, we show that Clique + Independent Set Deletion, which is a restriction of Cluster Deletion, admits a kernel of size O (k / log k) . We also obtain small kernels for several other edge modification problems. We first show that Cluster Deletion admits a 2k-vertex kernel as Cluster Editing, improving the previous 4k-vertex kernel. We prove that (Pseudo-)Split Completion (and the equivalent (Pseudo-)Split Deletion) admits a linear kernel, improving the existing quadratic kernel. We also prove that Trivially Perfect Completion admits a quadratic kernel (improving the cubic kernel), and finally prove that its triangle-free version (Starforest Deletion) admits a linear kernel, which is optimal under the Exponential Time Hypothesis. [ABSTRACT FROM AUTHOR]

Given a graph G with source and destination vertices s , t ∈ V (G) respectively, Tracking Paths asks for a minimum set of vertices T ⊆ V (G) , such that the sequence of vertices restricted to T encountered in each simple path from s to t is unique. The problem was proven NP -hard [3] and was found to admit a quadratic kernel when parameterized by the size of the desired solution [8]. Following recent trends, for the first time, we study Tracking Paths with respect to structural parameters of the input graph, parameters that measure how far the input graph is, from an easy instance. We prove that Tracking Paths admits fixed-parameter tractable (FPT) algorithms when parameterized by the following parameters: (i) size of a 2-dominating set, (ii) size of cluster vertex deletion set, and (iii) size of split deletion set. En route we also look at Vertex Cover parameterized by the size of edge clique cover and show it fixed-parameter tractable. • Tracking Paths is fixed-parameter tractable when parameterized by the size of a 2-dominating set. • Tracking Paths is fixed-parameter tractable when parameterized by the size of a cluster vertex deletion set. • Tracking Paths is fixed-parameter tractable when parameterized by the size of a split vertex deletion set. [ABSTRACT FROM AUTHOR]

The problem of computing induced subgraphs that satisfy some specified restrictions arises in various applications of graph algorithms and has been well studied. In this paper, we consider the following ▪ (▪) problem. The input is a graph G = (V , E) , with each vertex in the set V having an assigned color, " ▪ " or " ▪ ". We seek a maximum-cardinality subset V ′ ⊆ V of vertices that is ▪ (having exactly | V ′ | / 2 red vertices and | V ′ | / 2 blue vertices), such that the subgraph induced by the vertex set V ′ in G is connected. We show that the BCS problem is NP-hard, even for bipartite graphs G (with red/blue color assignment not necessarily being a proper 2-coloring). Further, we consider this problem on various graph classes, e.g., planar graphs, chordal graphs, trees, split graphs, bipartite graphs with a proper red/blue 2-coloring, and graphs with diameter 2. For each of these classes we either prove NP-hardness or design a polynomial time algorithm. [ABSTRACT FROM AUTHOR]

A (0, 1)-matrix has the consecutive-ones property (C1P) if its columns can be permuted to make the 1’s in each row appear consecutively. This property was characterized in terms of forbidden submatrices by Tucker in 1972. Several graph classes were characterized by means of this property, including interval graphs and strongly chordal digraphs. In this work, we define and characterize 2-nested matrices, which are (0, 1)-matrices with a variant of the C1P and for which there is also a certain assignment of one of two colors to each block of consecutive 1’s in each row. The characterization of 2-nested matrices in the present work is of key importance to characterize split graphs that are also circle by minimal forbidden induced subgraphs. [ABSTRACT FROM AUTHOR]

A domination coloring of a graph G is a proper vertex coloring of G, such that each vertex of G dominates at least one color class (possibly its own class), and each color class is dominated by at least one vertex. The minimum number of colors among all domination colorings is called the domination chromatic number, denoted by χ d d (G) . In this paper, we study the complexity of the k-domination coloring problem by proving its NP-completeness for arbitrary graphs. We give basic results and properties of χ d d (G) , including the bounds and characterization results, and further research χ d d (G) of some special classes of graphs, such as the split graphs, the generalized Petersen graphs, corona products, and edge corona products. Several results on graphs with χ d d (G) = χ (G) are presented. Moreover, an application of domination colorings in social networks is proposed. [ABSTRACT FROM AUTHOR]

In DEFECTIVE COLORING we are given a graphGand two integers χd;Δ* and are asked if we can χd-colorGso that the maximum degree induced by any color class is at mostΔ*. We show that this natural generalization of COLORING is much harder on several basic graph classes. In particular, we show that it is NP-hard on split graphs, even when one of the two parameters χd;Δ* is set to the smallest possible fixed value that does not trivialize the problem (χd = 2 or Δ* = 1). We also give a simple treewidth-based DP algorithm which, together with the aforementioned hardness for split graphs, also completely determines the complexity of the problem on chordal graphs. We then consider the case of cographs and show that, somewhat surprisingly, DEFECTIVE COLORING turns out to be one of the few natural problems which are NP-hard on this class. We complement this negative result by showing that DEFECTIVE COLORING is in P for cographs if either χd or Δ* is fixed; that it is in P for trivially perfect graphs; and that it admits a sub-exponential time algorithm for cographs when both χd and Δ* are unbounded. [ABSTRACT FROM AUTHOR]

For an optimization problem known to be NP-Hard, the dichotomy study investigates the reduction instances to determine the line separating polynomial-time solvable vs NP-Hard instances (easy vs hard instances). In this paper, we investigate the well-studied Hamiltonian cycle problem (HCYCLE), and present an interesting dichotomy result on split graphs. T. Akiyama et al. (1980) have shown that HCYCLE is NP-complete on planar bipartite graphs with maximum degree 3. We use this result to show that HCYCLE is NP-complete for K 1 , 5 -free split graphs. Further, we present polynomial-time algorithms for Hamiltonian cycle in K 1 , 3 -free and K 1 , 4 -free split graphs. We believe that the structural results presented in this paper can be used to show similar dichotomy result for Hamiltonian path problem and other variants of Hamiltonian cycle (path) problems. [ABSTRACT FROM AUTHOR]

A degree associated edge card of a graph G is an edge deleted subgraph of G with which the degree of the deleted edge is given. The degree associated edge reconstruction number of a graph G (or dern(G)) is the size of the smallest collection of the degree associated edge 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 dern of all split graphs with biregular independent set is one.

Abstract Background Microbiomes play vital roles in shaping environments and stabilize them based on their compositions and inter-species relationships among its species. Variations in microbial properties have been reported to have significant impact on their host environment. For example, variants in gut microbiomes have been reported to be associated with several chronic conditions, such as inflammatory disease and irritable bowel syndrome. However, how microbial bacteria contribute to pathogenesis still remains unclear and major research questions in this domain remain unanswered. Methods We propose a split graph model to represent the composition and interactions of a given microbiome. We used metagenomes from Korean populations in this study. The dataset consists of three different types of samples, viz. mucosal tissue and stool from Crohn’s disease patients and stool from healthy individuals. We use the split graph model to analyze the impact of microbial compositions on various host phenotypes. Utilizing the graph model, we have developed a pipeline that integrates genomic information and pathway analysis to characterize both critical informative components of inter-bacterial correlations and associations between bacterial taxa and various metabolic pathways. Results The obtained results highlight the importance of the microbial communities and their inter-relationships and show how these microbial structures are correlated with Crohn’s disease. We show that there are significant positive associations between detected taxonomic biomarkers as well as multiple functional modules in the split graph of mucosal tissue samples from CD patients. Bacteria Moraxellaceae and Pseudomonadaceae were detected as taxonomic biomarkers in CD groups. Higher abundance of these bacteria have been reported in previous study and several metabolic pathways associated with these bacteria were characterized in CD samples. Conclusions The proposed pipeline provides a new way to approach the analysis of complex microbiomes. The results obtained from this study show great potential in unraveling mechansims in complex biological systems to understand how various components in such complex environments are associated with critical biological functions.

An orientation D of a graph G = (V , E) is a digraph obtained from G by replacing each edge by exactly one of the two possible arcs with the same end vertices. For each v ∈ V (G) , the indegree of v in D , denoted by d D − (v) , is the number of arcs with head v in D. An orientation D of G is proper if d D − (u) ≠ d D − (v) , for all u v ∈ E (G). An orientation with maximum indegree at most k is called a k -orientation. The proper orientation number of G , denoted by χ → (G) , is the minimum integer k such that G admits a proper k -orientation. We prove that determining whether χ → (G) ≤ k is NP - complete for chordal graphs of bounded diameter, but can be solved in linear-time in the subclass of quasi-threshold graphs. When parameterizing by k , we argue that this problem is FPT for chordal graphs and argue that no polynomial kernel exists, unless NP ⊆ coNP / poly. We present a better kernel to the subclass of split graphs and a linear kernel to the class of cobipartite graphs. Concerning bounds, we first prove that if G is split, then χ → (G) ≤ 2 ω (G) − 2 and that if G is a k -uniform block graph, then χ → (G) ≤ 3 k − 2. These bounds are tight. We also present new families of trees having proper orientation number at most 2 and at most 3. Actually, we prove a general bound stating that any graph G having no adjacent vertices of degree at least c + 1 has proper orientation number at most c. This implies new classes of (outer)planar graphs with bounded proper orientation number. We also prove that maximal outerplanar graphs G whose weak-dual is a path satisfy χ → (G) ≤ 13. Finally, we present simple bounds to the classes of chordal claw-free graphs and cographs. [ABSTRACT FROM AUTHOR]

The chromatic index of a graph G , χ'(G), is the least number of colors of some edge coloring of G such that no two adjacent edges have the same color. Given a graph G and an integer k , to decide if χ'(G) ≤ k is NP-complete. A graph is an interval graph if it represents the intersection relation of a set of closed intervals in R. A graph is a split graph if its vertex set can be partitioned into a clique and an independent set. A graph is split-interval if it is simultaneously an interval and a split graph. In this paper we show how to determine the chromatic index of all split-interval graphs. Our proof leads to a polynomial-time algorithm to deciding if χ'(G) ≤ k given an integer k and a split-interval graph G. [ABSTRACT FROM AUTHOR]

In the Cluster Deletion problem the goal is to remove the minimum number of edges of a given graph, such that every connected component of the resulting graph constitutes a clique. It is known that the decision version of Cluster Deletion is NP-complete on ( P 5 -free) chordal graphs, whereas Cluster Deletion is solved in polynomial time on split graphs. However, the existence of a polynomial-time algorithm of Cluster Deletion on interval graphs, a proper subclass of chordal graphs, remained a well-known open problem. Our main contribution is that we settle this problem in the affirmative, by providing a polynomial-time algorithm for Cluster Deletion on interval graphs. Moreover, despite the simple formulation of a polynomial-time algorithm on split graphs, we show that Cluster Deletion remains NP-complete on a natural and slight generalization of split graphs that constitutes a proper subclass of P 5 -free chordal graphs. Although the later result arises from the already-known reduction for P 5 -free chordal graphs, we give an alternative proof showing an interesting connection between edge-weighted and vertex-weighted variations of the problem. To complement our results, we provide faster and simpler polynomial-time algorithms for Cluster Deletion on subclasses of such a generalization of split graphs. [ABSTRACT FROM AUTHOR]

When can we compute the diameter of a graph in quasi linear time? We address this question for the class of split graphs, that we observe to be the hardest instances for deciding whether the diameter is at most two. We stress that although the diameter of a non-complete split graph can only be either 2 or 3, under the Strong ExponentialTime Hypothesis (SETH) we cannot compute the diameter of an n-vertex m-edge split graph in less than quadratic time – in the size n + m of the input. Therefore it is worth to study the complexity of diameter computation on subclasses of split graphs, in order to better understand the complexity border. Specifically, we consider the split graphs with bounded clique-interval number and their complements, with the former being a natural variation of the concept of interval number for split graphs that we introduce in this paper. We first discuss the relations between the clique-interval number and other graph invariants such as the classic interval number of graphs, the treewidth, the VC-dimension and the stabbing number of a related hypergraph. Then, in part based on these above relations, we almost completely settle the complexity of diameter computation on these subclasses of split graphs: • For the k-clique-interval split graphs, we can compute their diameter in truly subquadratic time if k = O(1), and even in quasi linear time if k = o(log n) and in addition a corresponding ordering of the vertices in the clique is given. However, under SETH this cannot be done in truly subquadratic time for any k = ω(log n). • For the complements of k-clique-interval split graphs, we can compute their diameter in truly subquadratic time if k = O(1), and even in time O(km) if a corresponding ordering of the vertices in the stable set is given. Again this latter result is optimal under SETH up to polylogarithmic factors. Our findings raise the question whether a k-clique interval ordering can always be computed in quasi linear time. We prove that it is the case for k = 1 and for some subclasses such as bounded-treewidth split graphs, threshold graphs and comparability split graphs. Finally, we prove that some important subclasses of split graphs – including the ones mentioned above – have a bounded clique-interval number. [ABSTRACT FROM AUTHOR]

In this paper, we study split graphs and related classes of graphs from the perspective of their sequence of vertex degrees and an associated lattice under majorization. Following the work of Merris [16] , we define blocks [ α (π) | β (π) ] , where π is the degree sequence of a graph, and α (π) and β (π) are sequences arising from π. We use the block representation [ α (π) | β (π) ] to characterize membership in each of the following classes: unbalanced split graphs, balanced split graphs, pseudo-split graphs, and three kinds of Nordhaus-Gaddum graphs (defined in [5,3]). As in [16] , we form a poset under the relation majorization in which the elements are the blocks [ α (π) | β (π) ] representing split graphs with a fixed number of edges. We partition this poset in several interesting ways using what we call amphoras, and prove upward and downward closure results for blocks arising from different families of graphs. Finally, we show that the poset becomes a lattice when a maximum and minimum element are added, and we prove properties of the meet and join of two blocks. [ABSTRACT FROM AUTHOR]