On the bi-enhancement of chordal-bipartite probe graphs

Given a class C of graphs, a graph G=(V,E) is said to be a C-probe graph if there exists a stable (i.e., independent) set of vertices X⊆V and a set F of pairs of vertices of X such that the graph G^′=(V,E∪F) is in the class C. Recently, there has been increasing interest and research on a variety of C-probe graph classes, such as interval probe graphs, chordal probe graphs and chain probe graphs.In this paper we focus on chordal-bipartite probe graphs. We prove a structural result that if B is a bipartite graph with no chordless cycle of length strictly greater than 6, then B is chordal-bipartite probe if and only if a certain “enhanced” graph B^∗ is a chordal-bipartite graph. This theorem is analogous to a result on interval probe graphs in Zhang (1994) [18] and to one on chordal probe graphs in Golumbic and Lipshteyn (2004) [11].     

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.     

Hamiltonicity in connected regular graphs

In 1980, Jackson proved that every 2-connected k-regular graph with at most 3k vertices is Hamiltonian. This result has been extended in several papers. In this note, we determine the minimum number of vertices in a connected k-regular graph that is not Hamiltonian, and we also solve the analogous problem for Hamiltonian paths. Further, we characterize the smallest connected k-regular graphs without a Hamiltonian cycle.     

On the number of Go positions on lattice graphs

We use transfer matrix methods to determine bounds for the numbers of legal Go positions for various numbers of players on some planar lattice graphs, including square lattice graphs such as those on which the game is normally played. We also find bounds on limiting constants that describe the behaviour of the number of legal positions on these lattice graphs as the dimensions of the lattices tend to infinity. These results amount to giving bounds for some specific evaluations of Go polynomials on these graphs.     

Efficient dominating sets in circulant graphs with domination number prime

Cayley graphs of finite cyclic group ${\mathbb{Z}}_n$ are called circulant graphs and denoted by $\mathrm{Cay}({\mathbb{Z}}_n,S)$. For $\mathrm{Cay}({\mathbb{Z}}_n,S)$ with $\frac{n}{|S|+1}$ prime, we give a necessary and sufficient condition for the existence of efficient dominating sets and characterize completely all its efficient dominating 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.     

Perfectly colorable graphs

We define a perfect coloring of a graph G as a proper coloring of G such that every connected induced subgraph H of G uses exactly ω(H) many colors where ω(H) is the clique number of H. A graph is perfectly colorable if it admits a perfect coloring. We show that the class of perfectly colorable graphs is exactly the class of perfect paw-free graphs. It follows that perfectly colorable graphs can be recognized and colored in linear time.     

Oriented colorings of 2-outerplanar graphs

A graph G is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the outer face is outerplanar. The oriented chromatic number of an oriented graph H is defined as the minimum order of an oriented graph H^′ such that H has a homomorphism to H^′. In this paper, we prove that 2-outerplanar graphs are 4-degenerate. We also show that oriented 2-outerplanar graphs have a homomorphism to the Paley tournament QR₆₇, which implies that their (strong) oriented chromatic number is at most 67.     

On the total choosability of planar graphs and of sparse graphs

In the current paper, we prove the 11-total choosability of planar graphs with maximum degree Δ?8, the (Δ+1)-total choosability of 5-cycle-free planar graphs with maximum degree Δ?8, the 5-total choosability of graphs with maximum degree Δ=4 and maximum average degree mad<3, and the 4-total choosability of subcubic graphs with maximum average degree .     

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.     

Combinatorial algorithms for feedback problems in directed graphs

Given a weighted directed graph G=(V,A), the minimum feedback arc set problem consists of finding a minimum weight set of arcs A′⊆A such that the directed graph (V,A?A′) is acyclic. Similarly, the minimum feedback vertex set problem consists of finding a minimum weight set of vertices containing at least one vertex for each directed cycle. Both problems are NP-complete. We present simple combinatorial algorithms for these problems that achieve an approximation ratio bounded by the length, in terms of number of arcs, of a longest simple cycle of the digraph.     

Some results on acyclic edge coloring of plane graphs

An acyclic edge coloring of a graph is a proper edge coloring without bichromatic cycles. The acyclic chromatic index of a graph G, denoted by α^′(G), is the minimum number k such that G admits an acyclic edge coloring using k colors. Let G be a plane graph with maximum degree Δ and girth g. In this paper, we prove that α^′(G)=Δ(G) if one of the following conditions holds: (1) Δ?8 and g?7; (2) Δ?6 and g?8; (3) Δ?5 and g?9; (4) Δ?4 and g?10; (5) Δ?3 and g?14. We also improve slightly a result of A. Fiedorowicz et al. (2008) [7] by showing that every triangle-free plane graph admits an acyclic edge coloring using at most Δ(G)+5 colors.     

Nowhere-zero 3-flows in dihedral Cayley graphs

In this paper we prove that every k-valent Cayley graph of a dihedral group, where k?4, admits a nowhere-zero 3-flow.     

Maximumk-covering of weighted transitive graphs with applications

Consider a weighted transitive graph, where each vertex is assigned a positive weight. Given a positive integerk, the maximumk-covering problem is to findk disjoint cliques covering a set of vertices with maximum total weight. An 0(kn ²)-time algorithm to solve the problem in a transitive graph is proposed, wheren is the number of vertices. Based on the proposed algorithm the weighted version of a number of problems in VLSI layout (e.g.,k-layer topological via minimization), computational geometry (e.g., maximum multidimensionalk-chain), graph theory (e.g., maximumk-independent set in interval graphs), and sequence manipulation (e.g., maximum increasingk-subsequence) can be solved inO(kn ²), wheren is the input size.This Work was supported in part by the National Science Foundation under Grant MIP-8709074 and MIP-8921540.     

Antimagic labeling and canonical decomposition of graphs

An antimagic labeling of a connected graph with m edges is an injective assignment of labels from {1,…,m} to the edges such that the sums of incident labels are distinct at distinct vertices. Hartsfield and Ringel conjectured that every connected graph other than K₂ has an antimagic labeling. We prove this for the classes of split graphs and graphs decomposable under the canonical decomposition introduced by Tyshkevich. As a consequence, we provide a sufficient condition on graph degree sequences to guarantee an antimagic labeling.     

Addendum to: Maximum Weight Independent Sets in hole- and co-chair-free graphs

In Brandstädt and Giakoumakis [2], we reduce the Maximum Weight Independent Set (MWIS) problem on hole- and co-chair-free graphs to a corresponding problem on prime atoms. Here we refine these results by investigating atoms of prime graphs (avoiding the requirement that the graphs are prime and atoms) and also observe that the MWIS problem is solvable in polynomial time on (odd-hole, co-chair)-free 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.