Retractions of split graphs and End-orthodox split graphs

A retraction f of a graph G is an edge-preserving mapping of G with f(v)=v for all v∈V(H), where H is the subgraph induced by the range of f. A graph G is called End-orthodox (End-regular) if its endomorphism monoid End X is orthodox (regular) in the semigroup sense. It is known that a graph is End-orthodox if it is End-regular and the composition of any two retractions is also a retraction. The retractions of split graphs are given and End-orthodox split graphs are characterized.     

Diameter vulnerability of graphs

Let f(t, D) denote the maximum possible diameter of a graph obtained from a (t+1)-edge-connected graph of diameter D by deleting t edges. F.R.K. Chung and M.R. Garey have shown that for D≥4,(t+1)(D?2)≤ f(t, D)≤(t+1)D+t. Here we consider the cases D=2 and D=3 and show that f(t,2)=4 and $\text{3}\text{2t}\text{?3≤f(t,3)≤3}\text{2t}\text{+4}$ if t is large enough. We solve also the problem for the directed case (answering a question of F.R.K. Chung and M.R. Garey) by showing that if D ≥ 3 the diameter of a diagraph obtained from a (t + 1)-arc-connected digraph of order n by deleting t arcs is at most n?2t+1. In the case D=.....2, the maximum possible diameter of the resulting digraph is (like in the undirected case) 4. We also consider the same problem for vertices.     

Dynamically maintaining split graphs

We present an algorithm that supports operations for modifying a split graph by adding edges or vertices and deleting edges, such that after each modification the graph is repaired to become a split graph in a minimal way. In particular, if the graph is not split after the modification, the algorithm computes a minimal, or if desired even a minimum, split completion or deletion of the modified graph. The motivation for such operations is similar to the motivation for fully dynamic algorithms for particular graph classes. In our case we allow all modifications to the graph and repair, rather than allowing only the modifications that keep the graph split. Fully dynamic algorithms of the latter kind are known for split graphs [L. Ibarra, Fully dynamic algorithms for chordal graphs and split graphs, Technical Report DCS-262-IR, University of Victoria, Canada, 2000].Our results can be used to design linear time algorithms for some recognition and completion problems, where the input is supplied in an on-line fashion.     

Fully decomposable split graphs

We discuss various questions around partitioning a split graph into connected parts. Our main result is a polynomial time algorithm that decides whether a given split graph is fully decomposable, that is, whether it can be partitioned into connected parts of orders _α1,_α2,…,_αk${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k$ for every _α1,_α2,…,_αk${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k$ summing up to the order of the graph. In contrast, we show that the decision problem whether a given split graph can be partitioned into connected parts of orders _α1,_α2,…,_αk${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k$ for a given partition _α1,_α2,…,_αk${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k$ of the order of the graph, is NP-hard.     

Edge cosymmetric graphs

This study explores the structure of graphs which together with their complements are edge symmetric.     

The relationship between the threshold dimension of split graphs and various dimensional parameters

Let the coboxicity of a graph G be denoted by cob(G), and the threshold dimension by t(G). For fixed k≥3, determining if cob(G)≥k and t(G)≤k are both NP-complete problems. We show that if G is a comparability graph, then we can determine if cob(G)≤2 in polynomial time. This result shows that it is possible to determine if the interval dimension of a poset equals 2 in polynomial time. If the clique covering number of G is 2, we show that one can determine if t(G)≤2 in polynomial time. Sufficient conditions on G are given for cob(G)≤2 and for t(G)≤2.     

The toughness of split graphs

In this short note we argue that the toughness of split graphs can be computed in polynomial time. This solves an open problem from a recent paper by Kratsch et al. (Discrete Math. 150 (1996) 231–245).     

Graphic sequences and split graphs

The split graph K _rVK _s on r+s vertices is denoted by S _r,s. A graphic sequence π = (d ₁, d ₂, ···, d _n) is said to be potentially S _r,s-graphic if there is a realization of π containing S _r,s as a subgraph. In this paper, a simple sufficient condition for π to be potentially S _r,s-graphic is obtained, which extends an analogous condition for p to be potentially K _r+1-graphic due to Yin and Li (Discrete Math. 301 (2005) 218–227). As an application of this condition, we further determine the values of σ(S _r,s, n) for n ≥ 3r + 3s - 1.     

Diameter vulnerability of GC graphs

Concern over fault tolerance in the design of interconnection networks has stimulated interest in finding large graphs with maximum degree Δ and diameter D such that the subgraphs obtained by deleting any set of s vertices have diameter at most D′, this value being close to D or even equal to it. This is the so-called (Δ,D,D′,s)-problem. The purpose of this work has been to study this problem for s=1 on some families of generalized compound graphs. These graphs were designed by Gómez (Ars Combin. 29-B (1990) 33) as a contribution to the (Δ,D)-problem, that is, to the construction of graphs having maximum degree Δ, diameter D and an order large enough. When approaching the mentioned problem in these graphs, we realized that each of them could be redefined as a compound graph, the main graph being the underlying graph of a certain iterated line digraph. In fact, this new characterization has been the key point to prove in a suitable way that the graphs belonging to these families are solutions to the (Δ,D,D+1,1)-problem.     

Containment relations in split graphs

A graph containment problem is to decide whether one graph can be modified into some other graph by using a number of specified graph operations. We consider edge deletions, edge contractions, vertex deletions and vertex dissolutions as possible graph operations permitted. By allowing any combination of these four operations we capture the following ten problems: testing on (induced) minors, (induced) topological minors, (induced) subgraphs, (induced) spanning subgraphs, dissolutions and contractions. A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. Our results combined with existing results settle the parameterized complexity of all ten problems for split graphs.     

Edge searching weighted graphs

In traditional edge searching one tries to clean all of the edges in a graph employing the least number of searchers. It is assumed that each edge of the graph initially has a weight equal to one. In this paper we modify the problem and introduce the Weighted Edge Searching Problem by considering graphs with arbitrary positive integer weights assigned to its edges. We give bounds on the weighted search number in terms of related graph parameters including pathwidth. We characterize the graphs for which two searchers are sufficient to clear all edges. We show that for every weighted graph the minimum number of searchers needed for a not-necessarily-monotonic weighted edge search strategy is enough for a monotonic weighted edge search strategy, where each edge is cleaned only once. This result proves the NP-completeness of the problem.     

Toughness, hamiltonicity and split graphs

Related to Chvátal's famous conjecture stating that every 2-tough graph is hamiltonian, we study the relation of toughness and hamiltonicity on special classes of graphs.

First, we consider properties of graph classes related to hamiltonicity, traceability and toughness concepts and display some algorithmic consequences. Furthermore, we present a polynomial time algorithm deciding whether the toughness of a given split graph is less than one and show that deciding whether the toughness of a bipartite graph is exactly one is coNP-complete.

We show that every split graph is hamiltonian and that there is a sequence of non-hamiltonian split graphs with toughness converging to .     

A note on Hamiltonian split graphs

A necessary condition for the existence of a Hamiltonian cycle in split graphs is proved.     

Edge disjoint cycles in graphs

Ore proved in 1960 that if G is a graph of order n and the sum of the degrees of any pair of nonadjacent vertices is at least n, then G has a hamiltonian cycle. In 1986, Li Hao and Zhu Yongjin showed that if n ? 20 and the minimum degree δ is at least 5, then the graph G above contains at least two edge disjoint hamiltonian cycles. The result of this paper is that if n ? 2δ², then for any 3 ? l₁ ? l₂ ? ? ? l_k ? n, 1 = k = [(δ - 1)/2], such graph has K edge disjoint cycles with lengths l₁, l₂…l_k, respectively. In particular, when l₁ = l₂ = ? = l_k = n and k = [(δ - 1)/2], the graph contains [(δ - 1)/2] edge disjoint hamiltonian cycles.     

Edge coloring nearly bipartite graphs

We give a simple polynomial time algorithm to compute the chromatic index of graphs which can be made bipartite by deleting a vertex. An analysis of this algorithm shows that for such graphs, the chromatic index is the roundup of the fractional chromatic index.     

Edge clique cover of claw-free graphs

The smallest number of cliques, covering all edges of a graph , is called the (edge) clique cover number of and is denoted by . It is an easy observation that if is a line graph on vertices, then . G. Chen et al. [Discrete Math. 219 (2000), no. 1–3, 17–26; MR1761707] extended this observation to all quasi-line graphs and questioned if the same assertion holds for all claw-free graphs. In this paper, using the celebrated structure theorem of claw-free graphs due to Chudnovsky and Seymour, we give an affirmative answer to this question for all claw-free graphs with independence number at least three. In particular, we prove that if is a connected claw-free graph on vertices with three pairwise nonadjacent vertices, then and the equality holds if and only if is either the graph of icosahedron, or the complement of a graph on vertices called “twister” or the power of the cycle , for some positive integer .