On direct product cancellation of graphs

The direct product of graphs obeys a limited cancellation property. Lovász proved that if C has an odd cycle then A×C≅B×C if and only if A≅B, but cancellation can fail if C is bipartite. This note investigates the ways cancellation can fail. Given a graph A and a bipartite graph C, we classify the graphs B for which A×C≅B×C. Further, we give exact conditions on A that guarantee A×C≅B×C implies A≅B. Combined with Lovász’s result, this completely characterizes the situations in which cancellation holds or fails.     

Cancellation for two-dimensional unique factorization domains

We show that if A and B are finitely generated two-dimensional unique factorization domains over an algebraically closed field, then A[x]≅B[x] implies A≅B. The proof is an application of an algebraic technique involving the AK invariant which has previously been used to obtain other cancellation theorems.     

Zero Divisors Among Digraphs

A digraph C is called a zero divisor if there exist non-isomorphic digraphs A and B for which ${A \times C \cong B \times C}$ , where the operation is the direct product. In other words, C being a zero divisor means that cancellation property ${A \times C \cong B \times C \Rightarrow A \cong B}$ fails. Lovász proved that C is a zero divisor if and only if it admits a homomorphism into a disjoint union of directed cycles of prime lengths.Thus any digraph C that is homomorphically equivalent to a directed cycle (or path) is a zero divisor. Given such a zero divisor C and an arbitrary digraph A, we present a method of computing all solutions X to the digraph equation ${A \times C \cong X \times C}$ .     

A forbidden subgraph characterization of line-polar bipartite graphs

A graph is polar if the vertex set can be partitioned into A and B in such a way that the subgraph induced by A is a complete multipartite graph and the subgraph induced by B is a disjoint union of cliques. Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. However, recognizing polar graphs is an NP-complete problem in general. This led to the study of the polarity of special classes of graphs such as cographs and chordal graphs, cf. Ekim et al. (2008) [7] and [5]. In this paper, we study the polarity of line graphs and call a graph line-polar if its line graph is polar. We characterize line-polar bipartite graphs in terms of forbidden subgraphs. This answers a question raised in the fist reference mentioned above. Our characterization has already been used to develop a linear time algorithm for recognizing line-polar bipartite graphs, cf. Ekim (submitted for publication) [6].     

2K2 vertex-set partition into nonempty parts

A graph is 2K₂-partitionable if its vertex set can be partitioned into four nonempty parts A, B, C, D such that each vertex of A is adjacent to each vertex of B, and each vertex of C is adjacent to each vertex of D. Determining whether an arbitrary graph is 2K₂-partitionable is the only vertex-set partition problem into four nonempty parts according to external constraints whose computational complexity is open. We show that for C₄-free graphs, circular-arc graphs, spiders, P₄-sparse graphs, and bipartite graphs the 2K₂-partition problem can be solved in polynomial time.     

Game-perfect graphs

A graph coloring game introduced by Bodlaender (Int J Found Comput Sci 2:133–147, 1991) as coloring construction game is the following. Two players, Alice and Bob, alternately color vertices of a given graph G with a color from a given color set C, so that adjacent vertices receive distinct colors. Alice has the first move. The game ends if no move is possible any more. Alice wins if every vertex of G is colored at the end, otherwise Bob wins. We consider two variants of Bodlaender’s graph coloring game: one (A) in which Alice has the right to have the first move and to miss a turn, the other (B) in which Bob has these rights. These games define the A-game chromatic number resp. the B-game chromatic number of a graph. For such a variant g, a graph G is g-perfect if, for every induced subgraph H of G, the clique number of H equals the g-game chromatic number of H. We determine those graphs for which the game chromatic numbers are 2 and prove that the triangle-free B-perfect graphs are exactly the forests of stars, and the triangle-free A-perfect graphs are exactly the graphs each component of which is a complete bipartite graph or a complete bipartite graph minus one edge or a singleton. From these results we may easily derive the set of triangle-free game-perfect graphs with respect to Bodlaender’s original game. We also determine the B-perfect graphs with clique number 3. As a general result we prove that complements of bipartite graphs are A-perfect.      

Arithmetic of Finite Ordered Sets: Cancellation of Exponents,II

Garrett Birkhoff conjectured in 1942 that when A, B, P are finite posets satisfying A ^PB ^P, then AB. We show that this is true. Further, we introduce an operation C(A ^B), related to Garrett Birkhoff's exponentiation, and determine the structure of the algebra of isomorphism types of finite posets under the operations induced by A+B, A×B, and C(A ^B). Every finite +-indecomposable and ×-indecomposable poset A of more than one element is expressible for unique (up to isomorphism) E and P as AC(E ^P) where P is connected and E is indecomposable for all three operations.     

Atom-bond connectivity index of graphs

The recently introduced atom-bond connectivity (ABC) index has been applied up until now to study the stability of alkanes and the strain energy of cycloalkanes. Furtula et al. (2009) [3] obtained extremal ABC values for chemical trees, and also, it has been shown that the star K_1,n−1, has the maximal ABC value of trees. In this paper, we present the lower and upper bounds on ABC index of graphs and trees, and characterize graphs for which these bounds are best possible.     

Factorization of Sums of Polynomials

Let A and B be monic polynomials of the same degree. Given some (or all) information about the individual polynomials A and B, in particular about their factorizations, what can be said about the factorization of their sum C=A+B? We survey results of Fell, Mason and others, and expand upon them. The famous ‘abc conjecture’ of number theory is one obvious motivation for this investigation.     

On the extendability of Bi-Cayley graphs of finite abelian groups

Let G be a finite group and A a nonempty subset (possibly containing the identity element) of G. The Bi-Cayley graph X=BC(G,A) of G with respect to A is defined as the bipartite graph with vertex set G×{0,1} and edge set {{(g,0),(sg,1)}∣g∈G,s∈A}. A graph Γ admitting a perfect matching is called n-extendable if ∣V(Γ)∣≥2n+2 and every matching of size n in Γ can be extended to a perfect matching of Γ. In this paper, the extendability of Bi-Cayley graphs of finite abelian groups is explored. In particular, 2-extendable and 3-extendable Bi-Cayley graphs of finite abelian groups are characterized.     

On the telescope conjecture for module categories

In [H. Krause, O. Solberg, Applications of cotorsion pairs, J. London Math. Soc. 68 (2003) 631-650], the Telescope Conjecture was formulated for the module category of an artin algebra R as follows: “If C=(A,B) is a complete hereditary cotorsion pair in with A and B closed under direct limits, then ”. We extend this conjecture to arbitrary rings R, and show that it holds true if and only if the cotorsion pair C is of finite type. Then we prove the conjecture in the case when R is right noetherian and B has bounded injective dimension (thus, in particular, when C is any cotilting cotorsion pair). We also focus on the assumptions that A and B are closed under direct limits and on related closure properties, and detect several asymmetries in the properties of A and B.     

Sumsets contained in infinite sets of integers

If the positive integers are partitioned into a finite number of cells, then Hindman proved that there exists an infinite set B such that all finite, nonempty sums of distinct elements of B all belong to one cell of the partition. Erdös conjectured that if A is a set of integers with positive asymptotic density, then there exist infinite sets B and C such that B + C ? A. This conjecture is still unproved. This paper contains several results on sumsets contained in finite sets of integers. For example, if A is a set of integers of positive upper density, then for any n there exist sets B and F such that B has positive upper density, F has cardinality n, and B + F ? A.     

The intricacy of avoiding arrays is 2

Let A be any n×n array on the symbols [n], with at most one symbol in each cell. An n×n Latin square L avoids A if all entries in L differ from the corresponding entries in A. If A is split into two arrays B and C in a special way, there are Latin squares L_B and L_C avoiding B and C, respectively. In other words, the intricacy of avoiding arrays is 2, the number of arrays into which A has to be split.     

On the local structure of doubly laced crystals

Let g be a Lie algebra all of whose regular subalgebras of rank 2 are type A₁×A₁, A₂, or C₂, and let B be a crystal graph corresponding to a representation of g. We explicitly describe the local structure of B, confirming a conjecture of Stembridge.     

Polar cographs

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s,k)-polar if there exists a partition A,B of its vertex set such that A induces a complete s-partite graph (i.e., a collection of at most s disjoint stable sets with complete links between all sets) and B a disjoint union of at most k cliques (i.e., the complement of a complete k-partite graph).Recognizing a polar graph is known to be NP-complete. These graphs have not been extensively studied and no good characterization is known. Here we consider the class of polar graphs which are also cographs (graphs without induced path on four vertices). We provide a characterization in terms of forbidden subgraphs. Besides, we give an algorithm in time O(n) for finding a largest induced polar subgraph in cographs; this also serves as a polar cograph recognition algorithm. We examine also the monopolar cographs which are the (s,k)-polar cographs where min(s,k)?1. A characterization of these graphs by forbidden subgraphs is given. Some open questions related to polarity are discussed.     

Netlike partial cubes I. General properties

A set A of vertices of a graph G is C-convex if the vertex set of any cycle of the subgraph of G induced by the union of the intervals between each pair of elements of A is contained in A. A partial cube (isometric subgraph of a hypercube) is a netlike partial cube if, for each edge ab, the sets U_ab and U_ba are C-convex (U_ab being the set of all vertices closer to a than to b and adjacent to some vertices closer to b than to a, and vice versa for U_ba). Particular netlike partial cubes are median graphs, even cycles, benzenoid graphs and cellular bipartite graphs. In this paper we give different characterizations and properties of netlike partial cubes. In particular, as median graphs and cellular bipartite graphs, these graphs have a pre-hull number which is at most one, and moreover the convex hull of any isometric cycle of a netlike partial cube is, as in the case of bipartite cellular graphs, this cycle itself or, as in the case of median graphs, a hypercube. We also characterize the gated subgraphs of a netlike partial cube, and we show that the gated amalgam of two netlike partial cubes is a netlike partial cube.     

More on positive commutators

Let A and B be positive operators on a Banach lattice E such that the commutator C=AB−BA is also positive. The paper continues the investigation of the spectral properties of C initiated in J. Bra?i? et al. (in press) [3]. If the sum A+B is a Riesz operator and the commutator C is a power compact operator, then C is a quasi-nilpotent operator having a triangularizing chain of closed ideals of E. If we assume that the operator A is compact and the commutator AC−CA is positive, the operator C is quasi-nilpotent as well. We also show that the commutator C is not invertible provided the resolvent set of C is connected.     

Representation of tripotents and representations via tripotents

Let A be an algebra. An element A∈A is called tripotent if A³=A. We study the questions: if both A and B are tripotents, then: Under what conditions are A+B and AB tripotent? Under what conditions do A and B commute? We extend the partial order from the Hilbert space idempotents to the set of all tripotents and show that every normal tripotent is self-adjoint. For A=M_n(C) we describe the set of all finite sums of tripotents, the convex hull of tripotents and the set of all tripotents averages. We also give the new proof of rational trace matrix representations by Choi and Wu [2].     

Direct-sum cancellation for modules over real quadratic orders

Let R be an order in a real quadratic number field. We say that R has mixed cancellation, respectively, torsion-free cancellation if

L⊕M≅L⊕N⇒M≅N     

Bi-complement Reducible Graphs

We introduce a new family of bipartite graphs which is the bipartite analogue of the class ofcomplement reduciblegraphs orcographs. Abi-complement reduciblegraph orbi-cographis a bipartite graphG = (W ∪ B, E) that can be reduced to single vertices by recursively bi-complementing the edge set of all connected bipartite subgraphs. Thebi-complementedgraphofGis the graph having the same vertex setW ∪ BasG, while its edge set is equal toW × B − E. The aim of this paper is to show that there exists an equivalent definition of bi-cographs by three forbidden configurations. We also propose a tree representation for this class of graphs.