The Join of Split Graphs Whose Regular Endomorphisms Form a Monoid

In this paper, the regular endomorphisms of the join of split graphs are investigated. We give a condition under which the regular endomorphisms of the join of split graphs form a monoid.     

二部图的E-H-不可收缩性

By End（G） and hEnd（G） we denote the set of endomorphisms and half-strong endomorphisms of a graph G respectively. A graph G is said to be E-H-unretractive if End（G） = hEnd（G）. A general characterization of an E-H-unretractive graph seems to be difficult. In this paper, bipartite graphs with E-H-unretractivity are characterized explicitly.     

Split graphs whose half-strong endomorphisms form a monoid

In this paper,the half-strong,the locally strong and the quasi-strong endomorphisms of a split graph are investigated.Let X be a split graph and let End(X),hEnd(X),lEnd(X) and qEnd(X) be the endomorphism monoid,the set of all half-strong endomorphisms,the set of all locally strong endomorphisms and the set of all quasi-strong endomorphisms of X,respectively.The conditions under which hEnd(X) forms a submonoid of End(X) are given.It is shown that lEnd(X) = qEnd(X) for any split graph X.The conditions under which lEnd(X)(resp.qEnd(X)) forms a submonoid of End(X) are also given.In particular,if hEnd(X) forms a monoid,then lEnd(X)(resp.qEnd(X)) forms a monoid too.     

Unretractive and S-unretractive joins and lexicographic products of graphs

Graphs without proper endomorphisms are the subject of this article. It is shown that the join of two graphs has this property if and only if both summands have it, and that the lexicographic product of a complete graph or an odd circuit as first factors has this property if and only if the second factor has it. A somewhat stronger theorem is proved if the lexicographic product has no proper strong endomorphism. The corresponding result for the join is the same as for usual endomorphisms.     

Endomorphisms of graphs II. Various unretractive graphs

In this part of the article we investigate graphs for which different endomorphism monoids coincide. We consider endomorphisms, strong endomorphisms and automorphisms. Coincidences are investigated for joins of graphs and some lexicographic products. In an additional section the graphs with the respective properties are listed up to 8 vertices in two cases and up to 5 vertices in the remaining case.     

A generalization of de Bruijn graphs and classification of endomorphisms of Cuntz algebras by graph invariants

The classification problem of endomorphisms of the Cuntz algebra O_N\mathcal{O}_{N} is solved by using graph theory. We introduce permutative de Bruijn graphs as generalizations of de Bruijn graphs. Branching laws for a permutative endomorphism ρ of O_N\mathcal{O}_{N} are computed by using the permutative de Bruijn graph associated with ρ. According to this correspondence between endomorphisms and graphs, we classify permutative endomorphisms of O_N\mathcal{O}_{N} by graph invariants concretely.     

一族具有正则绐幺半群的图

本文给出了一族具有正则自同态么半群的图及相应的自同态计数公式．     

Endomorphism Spectra of Bipartite Graphs with Diameter Three and Girth Six

There are different endomorphisms for a graph. For a more systematic treatment of these endomorphisms the endomorphism spectrum and the endomorphism type of a graph are defined. Knauer characterized trees using their endomorphism types. The endomorphism type of bipartite graphs with diameter three and girth six is given in this paper.AMS Subject Classification (1991): 05C25 20M20Supported by the National Natural Science Foundation of China (19901012)     

Finite Invariant Sets for a Family of Endomorphisms in Compact Graphs

We prove several results concerning the existence of common invariant finite sets of vertices or of common invariant finite connected subgraphs for some families of endomorphisms of graphs whose ends are all dominated.     

Minimizing cyclic cutwidth of graphs using a memetic algorithm

Cyclic cutwidth minimization problem (CCMP) consists of embedding a graph onto a circle such that the maximum cutwidth in a region is minimized. It is an NP-complete problem and for some classes of graphs, exact results of cyclic cutwidth have been proved in literature. However, no algorithm has been reported for general graphs. In this paper, a memetic algorithm is proposed for CCMP in which we have designed six construction heuristics in order to generate a good initial population and also local search is employed to improve the solutions in each generational phase. The algorithm achieves optimal results for the classes of graphs with known exact results. Extensive experiments have also been conducted on some classes of graphs for which exact results are not known such as the complete split graph, join of hypercubes, toroidal meshes, cone graph and some instances of Harwell-Boeing graphs which are a subset of public domain Matrix Market library. Trends observed in the experimental results for some of the classes of graphs have led to conjectures for cyclic cutwidth.     

Functional graphs of rational maps induced by endomorphisms of ordinary elliptic curves over finite fields

In this paper we study the dynamics of rational maps induced by endomorphisms of ordinary elliptic curves defined over finite fields. For any such map we describe the cycle and the tree structures of the associated graphs.     

Circuit decompositions of join‐covered graphs

In this paper, we focus our attention on join‐covered graphs, that is, ±1‐weighted graphs, without negative circuits, in which every edge lies in a zero‐weight circuit. Join covered graphs are a natural generalization of matching‐covered graphs. Many important properties of matching covered graphs, such as the existence of a canonical partition, tight cut decomposition and ear decomposition, have been generalized to join covered graphs by A. Seb? [5]. In this paper we prove that any two edges of a join‐covered graph lie on a zero‐weight circuit (under an equivalent weighting), generalize this statement to an arbitrary number of edges, and characterize minimal bipartite join‐covered graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 220–233, 2009     

Ear decompositions of join covered graphs

Join covered graphs are ±1-weighted graphs, without negative circuits, in which every edge lies in a zero-weight circuit. Join covered graphs are a natural generalization of matching covered graphs. Many important properties of matching covered graphs have been generalized to join covered graphs. In this paper, we generalize Lovász and Plummerʼs ear decomposition theorem of matching covered graphs to join covered graphs.     

Graphs whose endomorphism monoids are regular

In this paper, we give several approaches to construct new End-regular (-orthodox) graphs by means of the join and the lexicographic product of two graphs with certain conditions. In particular, the join of two connected bipartite graphs with a regular (orthodox) endomorphism monoid is explicitly described.     

Chordal graphs and join spaces

A join space is an abstract model for partially ordered linear, spherical and projective geometries. A characterization for chordal graphs which are join spaces is given: a chordal graph is a join space if and only if it does not contain one of the two forbidden graphs as an induced subgraph.     

Split Permutation Graphs

The class of split permutation graphs is the intersection of two important classes, the split graphs and permutation graphs. It also contains an important subclass, the threshold graphs. The class of threshold graphs enjoys many nice properties. In particular, these graphs have bounded clique-width and they are well-quasi-ordered by the induced subgraph relation. It is known that neither of these two properties is extendable to split graphs or to permutation graphs. In the present paper, we study the question of extendability of these two properties to split permutation graphs. We answer this question negatively with respect to both properties. Moreover, we conjecture that with respect to both of them the split permutation graphs constitute a critical class.     

Minimal split completions

We study the problem of adding an inclusion minimal set of edges to a given arbitrary graph so that the resulting graph is a split graph, called a minimal split completion of the input graph. Minimal completions of arbitrary graphs into chordal and interval graphs have been studied previously, and new results have been added recently. We extend these previous results to split graphs by giving a linear-time algorithm for computing minimal split completions. We also give two characterizations of minimal split completions, which lead to a linear time algorithm for extracting a minimal split completion from any given split completion.We prove new properties of split graph that are both useful for our algorithms and interesting on their own. First, we present a new way of partitioning the vertices of a split graph uniquely into three subsets. Second, we prove that split graphs have the following property: given two split graphs on the same vertex set where one is a subgraph of the other, there is a sequence of edges that can be removed from the larger to obtain the smaller such that after each edge removal the modified graph is split.     

Edge Coloring of Split Graphs

A split graph is a graph whose vertex set admits a partition into a stable set and a clique. The chromatic indexes for some subsets of split graphs, such as split graphs with odd maximum degree and split-indifference graphs, are known. However, for the general class, the problem remains unsolved. This paper presents new results about the classification problem for split graphs as a contribution in the direction of solving the entire problem for this class.     

Coincidence of the sets of minimal and irreducible join graphs over primary structure of algebraic Bayesian networks

An algebraic Bayesian network (ABN) is a probabilistic-logic graphical model of bases of knowledge patterns with uncertainty. A primary structure of an ABN is a set of knowledge patterns, that are ideals of conjunctions of positive literals except the empty conjunction endowed with scalar or interval probability estimates. A secondary ABN structure is represented by a graph constructed over the primary structure, which is called a join graph. From the point of view of learning of a global ABN structure, of interest are join graphs with the minimum number of edges and irreducible join graphs. A theorem on the coincidence of the sets of minimal and irreducible join graphs over the same primary structure is proved. A greedy algorithm constructing an arbitrary minimal join graph from a given primary structure is described. A theorem expressing the number of edges in a minimal join graph as the sum of the ranks of the incidence matrices of strong restrictions of a maximal join graph minus the number of significant weights is stated and proved. A generalized graph of maximal knowledge patterns (GGMKP) is a graph with the same vertex set as the join graph which is not subject to any constraints concerning the possibility of joining two vertices by an edge. It is proved that the pair consisting of the edge set of a maximal GGMKP and the set of all subsets of this graph such that the subtraction of any such subset from the maximal GGMKP yields an edge of the join graph on the same vertex set is a matroid.     

Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition

We present efficient (parallel) algorithms for two hierarchical clustering heuristics. We point out that these heuristics can also be applied to solving some algorithmic problems in graphs, including split decomposition. We show that efficient parallel split decomposition induces an efficient parallel parity graph recognition algorithm. This is a consequence of the result of S. Cicerone and D. Di Stefano [[7]] that parity graphs are exactly those graphs that can be split decomposed into cliques and bipartite graphs.