Graph parameters measuring neighbourhoods in graphs—Bounds and applications

The neighbourhood-width of a graph G=(V,E) is introduced in [F. Gurski, Linear layouts measuring neighbourhoods in graphs, Discrete Math. 306 (15) (2006) 1637-1650.] as the smallest integer k such that there is a linear layout ?:V→{1,…,|V|} such that for every 1?i<|V| the vertices u with ?(u)?i can be divided into at most k subsets each members having the same neighbours with respect to the vertices v with ?(v)>i.In this paper we show first bounds for the neighbourhood-width of general graphs, caterpillars, trees and grid graphs and give applications of the layout parameter neighbourhood-width in graph drawing and VLSI design.     

Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges

A set of planar graphs {G₁(V,E₁),…,Gk(V,Ek)} admits a simultaneous embedding if they can be drawn on the same pointset P of order n in the Euclidean plane such that each point in P corresponds one-to-one to a vertex in V and each edge in Ei does not cross any other edge in Ei (except at endpoints) for i∈{1,…,k}. A fixed edge is an edge (u,v) that is drawn using the same simple curve for each graph Gi whose edge set Ei contains the edge (u,v). We give a necessary and sufficient condition for two graphs whose union is homeomorphic to K₅ or K3,3 to admit a simultaneous embedding with fixed edges (SEFE). This allows us to characterize the class of planar graphs that always have a SEFE with any other planar graph. We also characterize the class of biconnected outerplanar graphs that always have a SEFE with any other outerplanar graph. In both cases, we provide O(n⁴)-time algorithms to compute a SEFE.     

Minimum number of edges in graphs that are both P2- and Pi-connected

A simple graph with n vertices is called P_i-connected if any two distinct vertices are connected by an elementary path of length i. In this paper, lower bounds of the number of edges in graphs that are both P₂- and P_i-connected are obtained. Namely if $\text{i?}\text{1}\text{2}\text{(n+1)}$, then |E(G)|?((4i?5)/(2i?2))(n?1), and if $\text{i >}\text{1}\text{2}\text{(n+ 1)}$, then |E(G)|?2(n?1) apart from one exeptional graph. Furthermore, extremal graphs are determined in the former.     

A note on domination, girth and minimum degree

Let G be a graph of order n, minimum degree δ?2, girth g?5 and domination number γ. In 1990 Brigham and Dutton [Bounds on the domination number of a graph, Q. J. Math., Oxf. II. Ser. 41 (1990) 269-275] proved that γ?⌈n/2-g/6⌉. This result was recently improved by Volkmann [Upper bounds on the domination number of a graph in terms of diameter and girth, J. Combin. Math. Combin. Comput. 52 (2005) 131-141; An upper bound for the domination number of a graph in terms of order and girth, J. Combin. Math. Combin. Comput. 54 (2005) 195-212] who for i∈{1,2} determined a finite set of graphs G_i such that γ?⌈n/2-g/6-(3i+3)/6⌉ unless G is a cycle or G∈G_i.Our main result is that for every i∈N there is a finite set of graphs G_i such that γ?n/2-g/6-i unless G is a cycle or G∈G_i. Furthermore, we conjecture another improvement of Brigham and Dutton's bound and prove a weakened version of this conjecture.     

Forcing faces in plane bipartite graphs

Let Ω denote the class of connected plane bipartite graphs with no pendant edges. A finite face s of a graph G∈Ω is said to be a forcing face of G if the subgraph of G obtained by deleting all vertices of s together with their incident edges has exactly one perfect matching. This is a natural generalization of the concept of forcing hexagons in a hexagonal system introduced in Che and Chen [Forcing hexagons in hexagonal systems, MATCH Commun. Math. Comput. Chem. 56 (3) (2006) 649-668]. We prove that any connected plane bipartite graph with a forcing face is elementary. We also show that for any integers n and k with n?4 and n?k?0, there exists a plane elementary bipartite graph such that exactly k of the n finite faces of G are forcing. We then give a shorter proof for a recent result that a connected cubic plane bipartite graph G has at least two disjoint M-resonant faces for any perfect matching M of G, which is a main theorem in the paper [S. Bau, M.A. Henning, Matching transformation graphs of cubic bipartite plane graphs, Discrete Math. 262 (2003) 27-36]. As a corollary, any connected cubic plane bipartite graph has no forcing faces. Using the tool of Z-transformation graphs developed by Zhang et al. [Z-transformation graphs of perfect matchings of hexagonal systems, Discrete Math. 72 (1988) 405-415; Plane elementary bipartite graphs, Discrete Appl. Math. 105 (2000) 291-311], we characterize the plane elementary bipartite graphs whose finite faces are all forcing. We also obtain a necessary and sufficient condition for a finite face in a plane elementary bipartite graph to be forcing, which enables us to investigate the relationship between the existence of a forcing edge and the existence of a forcing face in a plane elementary bipartite graph, and find out that the former implies the latter but not vice versa. Moreover, we characterize the plane bipartite graphs that can be turned to have all finite faces forcing by subdivisions.     

Boxicity of Graphs on Surfaces

The boxicity of a graph G = (V, E) is the least integer k for which there exist k interval graphs G _i  = (V, E _i ), 1 ≤ i ≤ k, such that ${E = E_1 \cap \cdots \cap E_k}$ . Scheinerman proved in 1984 that outerplanar graphs have boxicity at most two and Thomassen proved in 1986 that planar graphs have boxicity at most three. In this note we prove that the boxicity of toroidal graphs is at most 7, and that the boxicity of graphs embeddable in a surface Σ of genus g is at most 5g + 3. This result yields improved bounds on the dimension of the adjacency poset of graphs on surfaces.     

On a cycle partition problem

Let G be any graph and let c(G) denote the circumference of G. We conjecture that for every pair c₁,c₂ of positive integers satisfying c₁+c₂=c(G), the vertex set of G admits a partition into two sets V₁ and V₂, such that V_i induces a graph of circumference at most c_i, i=1,2. We establish various results in support of the conjecture; e.g. it is observed that planar graphs, claw-free graphs, certain important classes of perfect graphs, and graphs without too many intersecting long cycles, satisfy the conjecture.This work is inspired by a well-known, long-standing, analogous conjecture involving paths.     

On a property of minimal triangulations

A graph H has the property MT, if for all graphs G, G is H-free if and only if every minimal (chordal) triangulation of G is H-free. We show that a graph H satisfies property MT if and only if H is edgeless, H is connected and is an induced subgraph of P₅, or H has two connected components and is an induced subgraph of 2P₃.This completes the results of Parra and Scheffler, who have shown that MT holds for H=P_k, the path on k vertices, if and only if k?5 [A. Parra, P. Scheffler, Characterizations and algorithmic applications of chordal graph embeddings, Discrete Applied Mathematics 79 (1997) 171-188], and of Meister, who proved that MT holds for ?P₂, ? copies of a P₂, if and only if ??2 [D. Meister, A complete characterisation of minimal triangulations of 2K₂-free graphs, Discrete Mathematics 306 (2006) 3327-3333].     

Double cycle covers and the petersen graph

Let O(G) denote the set of odd-degree vertices of a graph G. Let t ? N and let ??_t denote the family of graphs G whose edge set has a partition. E(g) = E₁ U E₂ U … U E_tsuch that O(G) = O(G[E_i]) (1 ? i ? t). This partition is associated with a double cycle cover of G. We show that if a graph G is at most 5 edges short of being 4-edge-connected, then exactly one of these holds: G ? ??₃, G has at least one cut-edge, or G is contractible to the Petersen graph. We also improve a sufficient condition of Jaeger for G ? ??_2p+1(p ? N).     

Vertex pancyclicity in quasi claw-free graphs

This paper generalizes the concept of locally connected graphs. A graph G is triangularly connected if for every pair of edges e₁,e₂∈E(G), G has a sequence of 3-cycles C₁,C₂,…,C_l such that e₁∈C₁,e₂∈C_l and E(C_i)∩E(C_i+1)≠∅ for 1?i?l-1. In this paper, we show that every triangularly connected quasi claw-free graph on at least three vertices is vertex pancyclic. Therefore, the conjecture proposed by Ainouche is solved.     

A maximum degree theorem for diameter-2-critical graphs

A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ?n ²/4? and that the extremal graphs are the complete bipartite graphs K _?n/2?,?n/2?. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n ₀ where n ₀ is a tower of 2’s of height about 10¹⁴. The conjecture has yet to be proven for other values of n. Let Δ denote the maximum degree of G. We prove the following maximum degree theorems for diameter-2-critical graphs. If Δ ≥ 0.7 n, then the Murty-Simon Conjecture is true. If n ≥ 2000 and Δ ≥ 0.6789 n, then the Murty-Simon Conjecture is true.     

Removable edges in a 5-connected graph and a construction method of 5-connected graphs

An edge e of a k-connected graph G is said to be a removable edge if G?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k-connected graphs have been investigated [D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465-473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187-193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245-256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217-228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74-87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434-438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k-connected graphs (k?5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K₆. For a k-connected graph G such that end vertices of any edge of G have at most k-3 common adjacent vertices, it is also proved that G has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K₆ by a number of θ⁺-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either K_k+1 or the graph H_k/2+1 obtained from K_k+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to K_k+1.     

The cochromatic index of a graph

We discuss partitions of the edge set of a graph into subsets which are uniform in their internal relationships; i.e., the edges are independent, they are incident with a common vertex (a star), or three edges meet in a triangle. We define the cochromatic index z′(G) of G to be the minimum number of subsets into which the edge set of G can be partitioned so that the edges in any subset are either mutually adjacent or independent.Several bounds for z′(G) are discussed. For example, it is shown that δ(G) - 1 ? z′(G)? Δ(G) + 1, with the lower bound being attained only for a complete graph. Here δ(G) and Δ(G) denote the minimum and maximum degrees of G, respectively. The cochromatic index is also found for complete n-partite graphs.Given a graph G define a sequence of graphs G₀, G₁,…, G_k, with G₀=G and

, with k being the first value of i for which G_i is regular. Let φ_i(G) = |V(G) – V(G_i| + Δ (G_i) and setφ(G) = min_0?i?kφ_i(G). We show that φ(G) ? 1 ?z′(G)?φ(G) + 1. We then s that a graph G is of class A, B or C, if z′(G) = φ(G) ? 1, φ(G), orφ(G) + 1, respectively. Examples of graphs of each class are presented; in particular, it is shown that any bipartite graph belongs to class B.Finally, we show that if a, b and c are positive integers with a?b?c + 1 and a?c, then unless a = c = b - 1 = 1, there exists a graph G having δ(G) = a, Δ(G) =c, and z′(G) = b.     

A note on Roman domination in graphs

Let G=(V,E) be a simple graph. A subset S⊆V is a dominating set of G, if for any vertex u∈V-S, there exists a vertex v∈S such that uv∈E. The domination number of G, γ(G), equals the minimum cardinality of a dominating set. A Roman dominating function on graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex v for which f(v)=0 is adjacent to at least one vertex u for which f(u)=2. The weight of a Roman dominating function is the value f(V)=∑_v∈Vf(v). The Roman domination number of a graph G, denoted by γ_R(G), equals the minimum weight of a Roman dominating function on G. In this paper, for any integer k(2?k?γ(G)), we give a characterization of graphs for which γ_R(G)=γ(G)+k, which settles an open problem in [E.J. Cockayne, P.M. Dreyer Jr, S.M. Hedetniemi et al. On Roman domination in graphs, Discrete Math. 278 (2004) 11-22].     

The complexity of generalized clique packing

The K_i - j packing problem P_{i, j} is defined as follows: Given a graph G and integer k does there exist a set of at least kK_i's in G such that no two of these K_i's intersect in more than j nodes. This problem includes such problems as matching, vertex partitioning into complete subgraphs and edge partitioning into complete subgraphs. In this paper it is shown thhat for i ? 3 and 0?j?i ?2 the P_{i, j} problems is NP-complete. Furthermore, the problems remains NP-complete for i?3 and 1?j?i ?2 for chordal graphs.     

Strong edge colorings of uniform graphs

For a graph G=(V(G),E(G)), a strong edge coloring of G is an edge coloring in which every color class is an induced matching. The strong chromatic index of G, χ_s(G), is the smallest number of colors in a strong edge coloring of G. The strong chromatic index of the random graph G(n,p) was considered in Discrete Math. 281 (2004) 129, Austral. J. Combin. 10 (1994) 97, Austral. J. Combin. 18 (1998) 219 and Combin. Probab. Comput. 11 (1) (2002) 103. In this paper, we consider χ_s(G) for a related class of graphs G known as uniform or ε-regular graphs. In particular, we prove that for 0<ε?d<1, all (d,ε)-regular bipartite graphs G=(U∪V,E) with |U|=|V|?n₀(d,ε) satisfy χ_s(G)?ζ(ε)Δ(G)², where ζ(ε)→0 as ε→0 (this order of magnitude is easily seen to be best possible). Our main tool in proving this statement is a powerful packing result of Pippenger and Spencer (Combin. Theory Ser. A 51(1) (1989) 24).     

Competitively Tight Graphs

The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x, v) and (y, v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of a graph G is the smallest number of such isolated vertices. Computing the competition number of a graph is an NP-hard problem in general and has been one of the important research problems in the study of competition graphs. Opsut [1982] showed that the competition number of a graph G is related to the edge clique cover number θ _E (G) of the graph G via θ _E (G) ? |V(G)| + 2 ≤ k(G) ≤ θ _E (G). We first show that for any positive integer m satisfying 2 ≤ m ≤ |V(G)|, there exists a graph G with k(G) = θ _E (G) ? |V(G)| + m and characterize a graph G satisfying k(G) = θ _E (G). We then focus on what we call competitively tight graphs G which satisfy the lower bound, i.e., k(G) = θ _E (G) ? |V(G)| + 2. We completely characterize the competitively tight graphs having at most two triangles. In addition, we provide a new upper bound for the competition number of a graph from which we derive a sufficient condition and a necessary condition for a graph to be competitively tight.     

4-regular claw-free IM-extendable graphs

A graph G is induced matching extendable (shortly, IM-extendable), if every induced matching of G is included in a perfect matching of G. A graph G is claw-free, if G does not contain any induced subgraph isomorphic to K_1,3. The kth power of a graph G, denoted by G^k, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. In this paper, the 4-regular claw-free IM-extendable graphs are characterized. It is shown that the only 4-regular claw-free connected IM-extendable graphs are , and T_r, r?2, where T_r is the graph with 4r vertices u_i,v_i,x_i,y_i, 1?i?r, such that for each i with 1?i?r, {u_i,v_i,x_i,y_i} is a clique of T_r and . We also show that a 4-regular strongly IM-extendable graph must be claw-free. As a consequence, the only 4-regular strongly IM-extendable graphs are K₄×K₂, and .     

Partition into cliques for cubic graphs: Planar case, complexity and approximation

Given a graph G=(V,E) and a positive integer k, the partition into cliques (pic) decision problem consists of deciding whether there exists a partition of V into k disjoint subsets V₁,V₂,…,V_k such that the subgraph induced by each part V_i is a complete subgraph (clique) of G. In this paper, we establish both the NP-completeness of pic for planar cubic graphs and the Max SNP-hardness of pic for cubic graphs. We present a deterministic polynomial time -approximation algorithm for finding clique partitions in maximum degree three graphs.     

Acyclic edge colouring of planar graphs without short cycles

Let G=(V,E) be any finite graph. A mapping C:E→[k] is called an acyclic edgek-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 which 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, denoted by .In 2001, Alon et al. conjectured that for any graph G it holds that ; here Δ(G) stands for the maximum degree of G.In this paper we prove this conjecture for planar graphs with girth at least 5 and for planar graphs not containing cycles of length 4,6,8 and 9. We also show that if G is planar with girth at least 6. Moreover, we find an upper bound for the acyclic chromatic index of planar graphs without cycles of length 4. Namely, we prove that if G is such a graph, then .