Minimum cycle bases of direct products of complete graphs

This paper presents a construction of a minimum cycle basis for the direct product of two complete graphs on three or more vertices. With the exception of two special cases, such bases consist entirely of triangles.     

On edge covering colorings of graphs

An edge covering coloring of a graph G is an edge-coloring of G such that each color appears at each vertex at least one time. The maximum integer k such that G has an edge covering coloring with k colors is called the edge covering chromatic index of G and denoted by . It is known that for any graph G with minimum degree δ(G), it holds that . Based on the subgraph of G induced by the vertices of minimum degree, we find a new sufficient condition for a graph G to satisfy . This result substantially extends a result of Wang et al. in 2006.     

Vertex vulnerability parameters of Kronecker products of complete graphs

Let G₁ and G₂ be two graphs. The Kronecker product G₁×G₂ of G₁ and G₂ has vertex set V(G₁×G₂)=V(G₁)×V(G₂) and edge set and v₁v₂∈E(G₂)}. In this paper, we determine some vertex vulnerability parameters of the Kronecker product of complete graphs Km×Kn for n?m?2 and n?3.     

A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs

We study a problem of lower bounds on straight line drawings of planar graphs. We show that at least 1.235·n points in the plane are required to draw each n-vertex planar graph with edges drawn as straight line segments (for sufficiently large n). This improves the previous best bound of 1.206·n (for sufficiently large n) due to Chrobak and Karloff [Sigact News 20 (4) (1989) 83-86]. Our contribution is twofold: we improve the lower bound itself and we give a significantly simpler and more straightforward proof.     

On the oriented chromatic number of Halin graphs

An oriented k-coloring of an oriented graph G is a mapping such that (i) if xy∈E(G) then c(x)≠c(y) and (ii) if xy,zt∈E(G) then c(x)=c(t)⇒c(y)≠c(z). The oriented chromatic number of an oriented graph G is defined as the smallest k such that G admits an oriented k-coloring. We prove in this paper that every Halin graph has oriented chromatic number at most 9, improving a previous bound proposed by Vignal.     

On edge colorings of 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that every 1-planar graph with maximum degree Δ?10 can be edge-colored with Δ colors.     

Acyclic edge colourings of graphs with the number of edges linearly bounded by the number of vertices

Let G be any finite graph. A mapping c:E(G)→{1,…,k} is called an acyclic edge k-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced in G by all the edges that have colour i or j is acyclic. The smallest number k of colours such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G and is denoted by .Determining the acyclic chromatic index of a graph is a hard problem, both from theoretical and algorithmical point of view. In 1991, Alon et al. proved that for any graph G of maximum degree Δ(G). This bound was later improved to 16Δ(G) by Molloy and Reed. In general, the problem of computing the acyclic chromatic index of a graph is NP-complete. Only a few algorithms for finding acyclic edge colourings have been known by now. Moreover, these algorithms work only for graphs from particular classes.In our paper, we prove that for every graph G which satisfies the condition that |E(G^′)|?t|V(G^′)|−1 for each subgraph G^′⊆G, where t?2 is a given integer, the constant p=2t³−3t+2. Based on that result, we obtain a polynomial algorithm which computes such a colouring. The class of graphs covered by our theorem is quite rich, for example, it contains all t-degenerate graphs.     

On disjoint maximal independent sets in graphs

An old problem in graph theory is to characterize the graphs that admit two disjoint maximal independent sets.     

Some optimization problems on weak-bisplit graphs

A new decomposition scheme for bipartite graphs namely canonical decomposition was introduced by Fouquet et al. [Internat. J. Found. Comput. Sci. 10 (1999) 513-533]. The so-called weak-bisplit graphs are totally decomposable following this decomposition. We present here some optimization problems for general bipartite graphs which have efficient solutions when dealing with weak-bisplit graphs.     

On graphs with the third largest number of maximal independent sets

Let G be a simple and undirected graph. By mi(G) we denote the number of maximal independent sets in G. Erd?s and Moser posed the problem to determine the maximum cardinality of mi(G) among all graphs of order n and to characterize the corresponding extremal graphs attaining this maximum cardinality. The above problem has been solved by Moon and Moser in [J.W. Moon, L. Moser, On cliques in graphs, Israel J. Math. 3 (1965) 23-28]. More recently, Jin and Li [Z. Jin, X. Li, Graphs with the second largest number of maximal independent sets, Discrete Mathematics 308 (2008) 5864-5870] investigated the second largest cardinality of mi(G) among all graphs of order n and characterized the extremal graph attaining this value of mi(G). In this paper, we shall determine the third largest cardinality of mi(G) among all graphs G of order n. Additionally, graphs achieving this value are also determined.     

About acyclic edge colourings of planar graphs

Let G=(V,E) be any finite simple graph. A mapping is called an acyclic edge k-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced by all the edges which have either colour i or j is acyclic. The smallest number k of colours, such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G and is denoted by .In 1991, Alon et al. [N. Alon, C.J.H. McDiarmid, B.A. Reed, Acyclic coloring of graphs, Random Structures and Algorithms 2 (1991) 277-288] proved that for any graph G of maximum degree Δ(G). This bound was later improved to 16Δ(G) by Molloy and Reed in [M. Molloy, B. Reed, Further algorithmic aspects of the local lemma, in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 524-529].In this paper we prove that for a planar graph G without cycles of length three and that the same holds if G has an edge-partition into two forests. We also show that if G is planar.     

Domination number of Cartesian products of directed cycles

Let γ(G) denote the domination number of a digraph G and let Cm□Cn denote the Cartesian product of Cm and Cn, the directed cycles of length m,n?2. In Liu et al. (2010) [11], we determined the exact values of γ(Cm□Cn) when m=2,3,4. In this paper, we give a lower and upper bounds for γ(Cm□Cn). Furthermore, we prove a necessary and sufficient conditions for Cm□Cn to have an efficient dominating set. Also, we determine the exact values: γ(C₅□Cn)=2n; γ(C₆□Cn)=2n if n≡0(mod 3), otherwise, γ(C₆□Cn)=2n+2; if m≡0(mod 3) and n≡0(mod 3).     

Non-contractible non-edges in 2-connected graphs

Any pair of non-adjacent vertices forms a non-edge in a graph. Contraction of a non-edge merges two non-adjacent vertices into a single vertex such that the edges incident on the non-adjacent vertices are now incident on the merged vertex. In this paper, we consider simple connected graphs, hence parallel edges are removed after contraction. The minimum number of nodes whose removal disconnects the graph is the connectivity of the graph. We say a graph is k-connected, if its connectivity is k. A non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. Otherwise the non-edge is non-contractible. We focus our study on non-contractible non-edges in 2-connected graphs. We show that cycles are the only 2-connected graphs in which every non-edge is non-contractible.     

Tutte type theorems for graphs having a perfect internal matching

Splitters are introduced to capture the meaning of barriers in graphs having a perfect internal matching. The factor-critical property is extended in a natural way to accommodate such graphs, and a characterization of factor-critical graphs is given in the new context. Two Tutte type theorems are presented for open graphs with perfect internal matchings, one on maximal splitters, and the other on maximal inaccessible splitters.     

Complexity of homomorphisms to direct products of graphs

For a graph G, OALG asks whether or not an input graph H together with a partial map g:S→G, S⊆V(H), admits a homomorphism f:H→G such that f|_S=g. We show that for connected graphs G₁, G₂, OAL G₁×G₂ is in P if G₁ and G₂ are trees and NP-complete otherwise.     

A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements

We introduce a simple, linear time algorithm for recognizing trivially perfect (TP) graphs. It improves upon the algorithm of Yan et al. [J.-H. Yan, J.-J. Chen, G.J. Chang, Quasi-threshold graphs, Discrete Appl. Math. 69 (3) (1996) 247–255] in that it is certifying, producing a P₄ or a C₄ when the graph is not TP. In addition, our algorithm can be easily modified to recognize the complement of TP graphs (co-TP) in linear time as well. It is based on lexicographic BFS, and in particular the technique of partition refinement, which has been used in the recognition of many other graph classes [D.G. Corneil, Lexicographic breadth first search—a survey, in: WG 2004, in: Lecture Notes in Comput. Sci., vol. 3353, Springer, 2004, pp. 1–19].     

On packing shortest cycles in graphs

We study the problems to find a maximum packing of shortest edge-disjoint cycles in a graph of given girth g (g-ESCP) and its vertex-disjoint analogue g-VSCP. In the case g=3, Caprara and Rizzi (2001) have shown that g-ESCP can be solved in polynomial time for graphs with maximum degree 4, but is APX-hard for graphs with maximum degree 5, while g-VSCP can be solved in polynomial time for graphs with maximum degree 3, but is APX-hard for graphs with maximum degree 4. For g∈{4,5}, we show that both problems allow polynomial time algorithms for instances with maximum degree 3, but are APX-hard for instances with maximum degree 4. For each g?6, both problems are APX-hard already for graphs with maximum degree 3.     

Super connectivity of Kronecker products of graphs

Let G₁ and G₂ be two connected graphs. The Kronecker product G₁×G₂ has vertex set V(G₁×G₂)=V(G₁)×V(G₂) and the edge set . In this paper, we show that if G is a bipartite graph with κ(G)=δ(G), then G×Kn(n?3) is super-κ.     

There exist oriented planar graphs with oriented chromatic number at least sixteen

We prove that there exist oriented planar graphs with oriented chromatic number at least 16. Using a result of Raspaud and Sopena [Inform. Process. Lett. 51 (1994) 171-174], this gives that the oriented chromatic number of the family of oriented planar graphs lies between 16 and 80.