A quasicancellation property for the direct product of graphs

We are motivated by the following question concerning the direct product of graphs. If A×C≅B×C, what can be said about the relationship between A and B? If cancellation fails, what properties must A and B share? We define a structural equivalence relation ∼ (called similarity) on graphs, weaker than isomorphism, for which A×C≅B×C implies A∼B. Thus cancellation holds, up to similarity. Moreover, if C is bipartite, then A×C≅B×C if and only if A∼B. We conjecture that the prime factorization of connected bipartite graphs is unique up to similarity of factors, and we offer some results supporting this conjecture.     

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.      

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.     

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

Permanental roots and the star degree of a graph

For undirected graphs, without loops or multiple edges, we define the star degree of a graph, and prove that it is equal to the multiplicity of the root 1 of per(xI ? B), where B = D + A. Considering bipartite graphs, we prove that per(xI ? B) = per(xI ? L), where L = D ? A, and consequently that the star degree of a bipartite graph can also be characterized by the multiplicity of the root 1 of per(xI ? L).     

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}$ .     

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.     

On the topological lower bound for the multichromatic number

In 1976, Stahl [14] defined the m-tuple coloring of a graph G and formulated a conjecture on the multichromatic number of Kneser graphs. For m=1 this conjecture is Kneser’s conjecture, which was proved by Lovász in 1978 [10]. Here we show that Lovász’s topological lower bound given in this way cannot be used to prove Stahl’s conjecture. We obtain that the strongest index bound only gives the trivial m⋅ω(G) lower bound if m≥|V(G)|. On the other hand, the connectivity bound for Kneser graphs is constant if m is sufficiently large. These findings provide new examples of graphs showing that the gaps between the chromatic number, the index bound and the connectivity bound can be arbitrarily large.     

Dual graph homomorphism functions

For any two graphs F and G, let hom(F,G) denote the number of homomorphisms F→G, that is, adjacency preserving maps V(F)→V(G) (graphs may have loops but no multiple edges). We characterize graph parameters f for which there exists a graph F such that f(G)=hom(F,G) for each graph G.The result may be considered as a certain dual of a characterization of graph parameters of the form hom(.,H), given by Freedman, Lovász and Schrijver [M. Freedman, L. Lovász, A. Schrijver, Reflection positivity, rank connectivity, and homomorphisms of graphs, J. Amer. Math. Soc. 20 (2007) 37-51]. The conditions amount to the multiplicativity of f and to the positive semidefiniteness of certain matrices N(f,k).     

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.     

On bipartite zero-divisor graphs

A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3.     

Menger's Theorem for Graphs Containing no Infinite Paths

Menger's theorem can be stated as follows: Let G = (V, E) be a finite graph, and let A and B be subsets of V. Then there exists a family F of vertex-disjoint paths from A to B and a subset S of V which separates A and B, such that S consists of a choice of precisely one vertex from each path in F.Erdös conjectured that in this form the theorem can be extended to infinite graphs. We prove this to be true for graphs containing no infinite paths, by showing that in this case the problem can be reduced to the case of bipartite graphs.     

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.     

Some isomorphisms between pairs of latin squares

Let A, B, C, D be latin squares with A orthogonal to B and C orthogonal to D. The pair A, B is isomorphic with the pair C, D if the graph of A, B is graph-isomorphic with the graph of C, D. A characterization is given for determining when a pair A, B of latin squares is isomorphic with a self-orthogonal square C and its transpose. Self-orthogonal squares are important because they are both abundant and easy to store. An algorithm either displays a self-orthogonal square C and an isomorphism from A, B to C, C^T or, if none exists, gives a small set of blocks to the existence of such a square isomorphism.     

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.     

A sufficient connectivity condition for generic rigidity in the plane

A graph G=(V,E) is said to be 6-mixed-connected if G−U−D is connected for all sets U⊆V and D⊆E which satisfy 2|U|+|D|≤5. In this note we prove that 6-mixed-connected graphs are (redundantly globally) rigid in the plane. This improves on a previous result of Lovász and Yemini.     

A characterization of Delsarte’s linear programming bound as a ratio bound

It is well known that the ratio bound is an upper bound on the stability number α(G) of a regular graph G. In this note it is proved that, if G is a graph whose edge is a union of classes of a symmetric association scheme, the Delsarte’s linear programming bound can alternatively be stated as the minimum of a set of ratio bounds. This result follows from a recently established relationship between a set of convex quadratic bounds on α(G) and the number ?′(G), a well known variant of the Lovász theta number, which was introduced independently by Schrijver [A. Schrijver, A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory 25 (1979) 425-429] and McEliece et al. [R.J. McEliece, E.R. Rodemich, H.C. Rumsey Jr, The Lovász bound and some generalizations, J. Combin. Inform. System Sci. 3 (1978) 134-152].