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.     

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.     

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 .     

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).     

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.     

On F-almost split sequences

Let A be an Artinian algebra and F an additive subbifunctor of Ext,（-, -） having enough projectives and injectives. We prove that the dualizing subvarieties of mod A closed under F-extensions have F-almost split sequences. Let T be an F-cotilting module in mod A and S a cotilting module over F = End（T）. Then Horn（-, T） induces a duality between F-almost split sequences in ⊥FT and almost sl31it sequences in ⊥S, where addrS = Hom∧（f（F）, T）. Let A be an F-Gorenstein algebra, T a strong F-cotilting module and 0→A→B→C→0 and F-almost split sequence in ⊥FT.If the injective dimension of S as a Г-module is equal to d, then C≌（ΩCM^-dΩ^dDTrA^＊）^＊,where（-）^＊=Hom（g,T）.In addition, if the F-injective dimension of A is equal to d, then A≌ΩMF^-dDΩFop^-d TrC≌ΩCMF^-d ≌F^d DTrC.     

A note on Hamiltonian split graphs

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

Graphic sequences with unique realization

A realization of an integer sequence means a graph which has this sequence as its degree sequence. This paper gives some characterizations of the sequences with unique labeled realization and also provides an effcient algorithm for testing if a sequence has a unique unlabeled realization.     

Cayley graphs and automatic sequences

We study those automatic sequences which are produced by an automaton whose underlying graph is the Cayley graph of a finite group. For 2-automatic sequences, we find a characterization in terms of what we call homogeneity, and among homogeneous sequences, we single out those enjoying what we call self-similarity. It turns out that 2-self-similar sequences (viewed up to a permutation of their alphabet) are in bijection with many interesting objects, for example dessins d’enfants (covers of the Riemann sphere with three points removed). For any p, we show that, in the case of an automatic sequence produced “by a Cayley graph,” the group and indeed the automaton can be recovered canonically from the sequence. Further, we show that a rational fraction may be associated with any automatic sequence. To compute this fraction explicitly, knowledge of a certain graph is required. We prove that for the sequences studied in the first part, the graph is simply the Cayley graph that we start from, and so calculations are possible. We give applications to the study of the frequencies of letters.     

Eccentric sequences in graphs

The eccentricitye(v) of a vertexv of a connected graphG is the maximum distance fromv among the vertices ofG. A nondecreasing sequencea ₁,a ₂, ...,a _p of nonnegative integers is said to be an eccentric sequence if there exists a connected graphG of orderp whose vertices can be labelledv ₁,v ₂, ...,v _p so thate(v _i )=a _i for alli. Several properties of eccentric sequences are exhibited, and a necessary and sufficient condition for a sequence to be eccentric is presented. Sequences which are the eccentricity sequences of trees are characterized. Some properties of the eccentricity sequences of self-complementary graphs are obtained. It is shown that the radius of a nontrivial self-complementary graph is two.     

Frequency sequences in graphs

Frequency sequences for trees and general graphs are considered. A necessary and sufficient condition is given for a sequence of numbers to be the frequency sequence of a tree.     

Relations between graphs and integer-pair sequences

In this paper a relation between graphs and finite integer-pair sequences is established. Necessary and sufficient conditions under which a given finite sequence of pairs of integers can realize a graph are found. Results are extended to diagraphs.     

Almost split sequences in tri-exact categories

We study the existence of almost split sequences in tri-exact categories, that is, extension-closed subcategories of triangulated categories. Our results unify and extend a number of existence theorems for almost split sequences in abelian categories and exact categories (that is, extension-closed subcategories of abelian categories), and those for almost split triangles in triangulated categories by numerous researchers. As applications, we obtain some new results on the existence of almost split triangles in the derived categories of all modules over an algebra with a unity or a locally finite dimensional algebra given by a quiver with relations.     

Score sequences of oriented graphs

We extend Landau's concept of the score structure of a tournament to that of the score sequence of an oriented graph, and give a condition for an arbitrary integer sequence to be a score sequence. The proof is by construction of a specific oriented graph Δ(S) with given score sequence S. It is shown that Δ(S) is transitive and has the minimum number of arcs among the oriented graphs with score sequence S.