Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid

Given an undirected graph G=(V,E) with matching number ν(G), a d-blocker is a subset of edges B such that ν((V,E?B))≤ν(G)−d and a d-transversal T is a subset of edges such that every maximum matching M has |M∩T|≥d. While the associated decision problem is NP-complete in bipartite graphs we show how to construct efficiently minimum d-transversals and minimum d-blockers in the special cases where G is a grid graph or a tree.     

Unbalanced bipartite factorizations of complete bipartite graphs

We construct a new infinite family of factorizations of complete bipartite graphs by factors all of whose components are copies of a (fixed) complete bipartite graph K_p,q. There are simple necessary conditions for such factorizations to exist. The family constructed here demonstrates sufficiency in many new cases. In particular, the conditions are always sufficient when q=p+1.     

Some Remarks on the Graph Γ I (R)

Let R be a commutative ring with nonzero identity and Z(R) its set of zero-divisors. The zero-divisor graph of R is Γ(R), with vertices Z(R)?{0} and distinct vertices x and y are adjacent if and only if xy = 0. For a proper ideal I of R, the ideal-based zero-divisor graph of R is Γ _I (R), with vertices {x ∈ R?I | xy ∈ I for some y ∈ R?I} and distinct vertices x and y are adjacent if and only if xy ∈ I. In this article, we study the relationship between the two graphs Γ(R) and Γ _I (R). We also determine when Γ _I (R) is either a complete graph or a complete bipartite graph and investigate when Γ _I (R) ? Γ(S) for some commutative ring S.     

Invalid proofs on incidence coloring

Incidence coloring of a graph G is a mapping from the set of incidences to a color-set C such that adjacent incidences of G are assigned distinct colors. Since 1993, numerous fruitful results as regards incidence coloring have been proved. However, some of them are incorrect. We remedy the error of the proof in [R.A. Brualdi, J.J.Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993) 51-58] concerning complete bipartite graphs. Also, we give an example to show that an outerplanar graph with Δ=4 is not 5-incidence colorable, which contradicts [S.D. Wang, D.L. Chen, S.C. Pang, The incidence coloring number of Halin graphs and outerplanar graphs, Discrete Math. 256 (2002) 397-405], and prove that the incidence chromatic number of the outerplanar graph with Δ≥7 is Δ+1. Moreover, we prove that the incidence chromatic number of the cubic Halin graph is 5. Finally, to improve the lower bound of the incidence chromatic number, we give some sufficient conditions for graphs that cannot be (Δ+1)-incidence colorable.     

图K_n和K_(n,n)的7-匹配设计和简单设计(英)

本文结出图K_n和K_(n,n)的7-匹配设计的存在性和由两个简单的（n，k，λ）-设计（i＝1，2）构造简单的（n，k，λ＋λ_2）设计的条件．     

Some results on integral sum graphs

Let Z denote the set of all integers. The integral sum graph of a finite subset S of Z is the graph (S,E) with vertex set S and edge set E such that for u,vS, uvE if and only if u+vS. A graph G is called an integral sum graph if it is isomorphic to the integral sum graph of some finite subset S of Z. The integral sum number of a given graph G, denoted by ζ(G), is the smallest number of isolated vertices which when added to G result in an integral sum graph. Let x denote the least integer not less than the real x. In this paper, we (i) determine the value of ζ(K_n−E(K_r)) for r2n/3−1, (ii) obtain a lower bound for ζ(K_n−E(K_r)) when 2r<2n/3−1 and n5, showing by construction that the bound is sharp when r=2, and (iii) determine the value of ζ(K_r,r) for r2. These results provide partial solutions to two problems posed by Harary (Discrete Math. 124 (1994) 101–108). Finally, we furnish a counterexample to a result on the sum number of K_r,s given by Hartsfiedl and Smyth (Graphs and Matrices, R. Rees (Ed.), Marcel, Dekker, New York, 1992, pp. 205–211).     

Realizing disjoint degree sequences of span at most two: A tractable discrete tomography problem

We consider the problem of coloring a grid using p colors with the requirement that each row and each column has a specific total number of entries of each color.Ryser (1957) [20], and independently Gale (1957) [10], obtained a necessary and sufficient condition for the existence of such a coloring when two colors are considered. This characterization yields a linear-time algorithm for constructing the coloring when it exists. Later, Gardner et al. (2000) [11], and Chrobak and Dürr (2001) [5], showed that the problem is NP-hard when p?7 and p?4, respectively.The case p=3 was an open problem for several years and has been recently settled by Dürr et al. (2009) [9]: it is NP-hard too. This grid coloring problem is equivalent to finding disjoint realizations of two degree sequences d₁,d₂ in a complete bipartite graph K_X,Y. These kinds of questions are well studied when one of the degree sequences has span zero or one, where the span of a function is the difference between its maximum and its minimum values. In [4], Chen and Shastri (1989) showed a necessary and sufficient condition for the existence of a coloring when d₁+d₂ restricted to X or Y has span at most one. In terms of discrete tomography this latter condition means that for two colors, the sum of the number of occurrences of these colors in each row is k or k+1, for some integer k.In the present paper we prove an analog to Chen and Shastri’s characterization when d₁+d₂ restricted to X and to Y has span at most two. That is, there exist integers k₁ and k₂ such that the sum of the number of occurrences of two of the colors in each row is k₁−1,k₁ or k₁+1, and in each column is k₂−1,k₂ or k₂+1. Our characterization relies on a new natural condition called the total saturation condition which, when not satisfied, gives a non-existence certificate of such a coloring that can be checked in polynomial time.     

A note on the domination dot-critical graphs

A graph G is dot-critical if contracting any edge decreases the domination number. Nader Jafari Rad (2009) [3] posed the problem: Is it true that a connected k-dot-critical graph G with G^′=0? is 2-connected? In this note, we give a family of 1-connected 2k-dot-critical graph with G^′=0? and show that this problem has a negative answer.     

On the number of transversals in Cayley tables of cyclic groups

It is well known that if n is even, the addition table for the integers modulo n (which we denote by B_n) possesses no transversals. We show that if n is odd, then the number of transversals in B_n is at least exponential in n. Equivalently, for odd n, the number of diagonally cyclic latin squares of order n, the number of complete mappings or orthomorphisms of the cyclic group of order n, the number of magic juggling sequences of period n and the number of placements of n non-attacking semi-queens on an n×n toroidal chessboard are at least exponential in n. For all large n we show that there is a latin square of order n with at least (3.246)ⁿ transversals.We diagnose all possible sizes for the intersection of two transversals in B_n and use this result to complete the spectrum of possible sizes of homogeneous latin bitrades.We also briefly explore potential applications of our results in constructing random mutually orthogonal latin squares.     

Minimum size transversals in uniform hypergraphs

A set of vertices in a hypergraph which meets all the edges is called a transversal. The transversal number τ(H)$\tau \left(H\right)$ of a hypergraph H$H$ is the minimum cardinality of a transversal in H$H$. A classical greedy algorithm for constructing a transversal of small size selects in each step a vertex which has the largest degree in the hypergraph formed by the edges not met yet. The analysis of this algorithm (by Chvátal and McDiarmid (1992)  [3]) gave some upper bounds for τ(H)$\tau \left(H\right)$ in a uniform hypergraph H$H$ with a given number of vertices and edges. We discuss a variation of this greedy algorithm. Analyzing this new algorithm, we obtain upper bounds for τ(H)$\tau \left(H\right)$ which improve the bounds by Chvátal and McDiarmid.     

Multicolored forests in complete bipartite graphs

If the edges of a graph G are colored using k colors, we consider the color distribution for this coloring a=(a₁,a₂,…,a_k), in which a_i denotes the number of edges of color i for i=1,2,…,k. We find inequalities and majorization conditions on color distributions of the complete bipartite graph K_n,n which guarantee the existence of multicolored subgraphs: in particular, multicolored forests and trees. We end with a conjecture on partitions of K_n,n into multicolored trees.     

On the Decomposition of Graphs into Complete Bipartite Graphs

In a complete bipartite decomposition π of a graph, we consider the number ϑ(v;π) of complete bipartite subgraphs incident with a vertex v. Let ϑ(G)= ϑ(v;π). In this paper the exact values of ϑ(G) for complete graphs and hypercubes and a sharp upper bound on ϑ(G) for planar graphs are provided, respectively. An open problem proposed by P.C. Fishburn and P.L. Hammer is solved as well.     

The rainbow number of matchings in regular bipartite graphs

Given a graph G and a subgraph H of G, let rb(G,H) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H. The number rb(G,H) is called the rainbow number of H with respect to G. Denote as mK₂ a matching of size m and as B_n,k the set of all the k-regular bipartite graphs with bipartition (X,Y) such that X=Y=n and k≤n. Let k,m,n be given positive integers, where k≥3, m≥2 and n>3(m−1). We show that for every GB_n,k, rb(G,mK₂)=k(m−2)+2. We also determine the rainbow numbers of matchings in paths and cycles.     

图的匹配设计的矩阵构造法

完全图Ｋ_ｎ（完全二部图Ｋ_ｎ,ｎ）的一个ｋ－匹配的集合Ｍ,若满足：Ｋ_ｎ（Ｋ_ｎ,ｎ）的每一对独立边恰出现在Ｍ的λ个元素中,则称Ｍ为一个匹配设计,记为ＭＡＴＣＨ（ｎ,ｋ,λ）（ＢＩＭＡＴＣＨ（ｎ;ｋ,λ））一设计．本文定义两个匹配设计对应的矩阵,并以此构造出某些新的匹配设计．     

A note on acyclic edge coloring of complete bipartite graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a^′(G). Let Δ=Δ(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by K_n,n. Alon, McDiarmid and Reed observed that a^′(K_p−1,p−1)=p for every prime p. In this paper we prove that a^′(K_p,p)≤p+2=Δ+2 when p is prime. Basavaraju, Chandran and Kummini proved that a^′(K_n,n)≥n+2=Δ+2 when n is odd, which combined with our result implies that a^′(K_p,p)=p+2=Δ+2 when p is an odd prime. Moreover we show that if we remove any edge from K_p,p, the resulting graph is acyclically Δ+1=p+1-edge-colorable.     

图Pn∨Km,n的全色数

对两个不交的图G,H,V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪{uv u∈V(G),v∈(H)},G∨H称为G和H的联图.本文得到了路Pn与完全二部图Km,n的联图Pn∨Km,n的全色数.