Generalized Thrackle Drawings of Non-bipartite Graphs

A graph drawing is called a generalized thrackle if every pair of edges meets an odd number of times. In a previous paper, we showed that a bipartite graph G can be drawn as a generalized thrackle on an oriented closed surface M if and only if G can be embedded in M. In this paper, we use Lins’ notion of a parity embedding and show that a non-bipartite graph can be drawn as a generalized thrackle on an oriented closed surface M if and only if there is a parity embedding of G in a closed non-orientable surface of Euler characteristic χ(M)−1. As a corollary, we prove a sharp upper bound for the number of edges of a simple generalized thrackle.     

Outerplanar Thrackles

We show that a graph drawing is an outerplanar thrackle if and only if, up to an inversion in the plane, it is Reidemeister equivalent to an odd musquash. This establishes Conway’s thrackle conjecture for outerplanar thrackles. We also extend this result in two directions. First, we show that no pair of vertices of an outerplanar thrackle can be joined by an edge in such a way that the resulting graph drawing is a thrackle. Secondly, we introduce the notion of crossing rank; drawings with crossing rank 0 are generalizations of outerplanar drawings. We show that all thrackles of crossing rank 0 are outerplanar. We also introduce the notion of an alternating cycle drawing, and we show that a thrackled cycle is alternating if and only if it is outerplanar.     

Great-circle tree thrackles

A thrackle is a graph drawing in which every pair of edges meets exactly once. Conway's Thrackle Conjecture states that the number of edges of a thrackle cannot exceed the number of its vertices. Cairns et al. (2015) [1] prove that the Thrackle Conjecture holds for great-circle thrackles drawn on the sphere. They also posit that Conway's Thrackle Conjecture can be restated to say that a graph can be drawn as a thrackle drawing in the plane if and only if it admits a great-circle thrackle drawing. We demonstrate that the class of great-circle thrackleable graphs excludes some trees. Thus the informal conjecture from Cairns et al. (2015) [1] is not equivalent to the Thrackle Conjecture.     

A Necessary and Sufficient Condition for the Existence of a Heterochromatic Spanning Tree in a Graph

We prove the following theorem. An edge-colored (not necessary to be proper) connected graph G of order n has a heterochromatic spanning tree if and only if for any r colors (1≤r≤n−2), the removal of all the edges colored with these r colors from G results in a graph having at most r+1 components, where a heterochromatic spanning tree is a spanning tree whose edges have distinct colors.     

On minimally 3-connected graphs on a surface

It is well known that the maximal size of minimally 3-connected graphs of order n ≥ 7 is 3n-9. In this paper, we shall prove that if G is a minimally 3-connected graph of order n, and is embedded in a closed surface with Euler characteristic χ, then G contains at most 2n- min {2, 2χ} edges. This bound is best possible for every closed surface.     

On Characterizations of Rigid Graphs in the Plane Using Spanning Trees

We study characterizations of generic rigid graphs and generic circuits in the plane using only few decompositions into spanning trees. Generic rigid graphs in the plane can be characterized by spanning tree decompositions [5,6]. A graph G with n vertices and 2n − 3 edges is generic rigid in the plane if and only if doubling any edge results in a graph which is the union of two spanning trees. This requires 2n − 3 decompositions into spanning trees. We show that n − 2 decompositions suffice: only edges of G − T can be doubled where T is a spanning tree of G. A recent result on tensegrity frameworks by Recski [7] implies a characterization of generic circuits in the plane. A graph G with n vertices and 2n − 2 edges is a generic circuit in the plane if and only if replacing any edge of G by any (possibly new) edge results in a graph which is the union of two spanning trees. This requires decompositions into spanning trees. We show that 2n − 2 decompositions suffice. Let be any circular order of edges of G (i.e. ). The graph G is a generic circuit in the plane if and only if is the union of two spanning trees for any . Furthermore, we show that only n decompositions into spanning trees suffice.     

<Emphasis Type="Italic">k</Emphasis>-factors in regular graphs

Plesnik in 1972 proved that an （m - 1）-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular （2n ＋ 1）-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and （or） excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik＇s result and the results obtained by Liu et al. in 1998, and improve Katerinis＇ result obtained 1993. Furthermore, we show that the results in this paper are the best possible.     

On κ—ordered Graphs Involved Degree Sum

A graph G is κ-ordered Hamiltonian 2≤κ≤n,if for every ordered sequence S of κ distinct vertices of G,there exists a Hamiltonian cycle that encounters S in the given order,In this article,we prove that if G is a graph on n vertices with degree sum of nonadjacent vertices at least n 3κ-9/2,then G is κ-ordered Hamiltonian for κ=3,4,…,[n/19].We also show that the degree sum bound can be reduced to n 2[κ/2]-2 if κ(G）≥3κ-1/2 or δ（G）≥5κ-4.Several known results are generalized.     

An upper bound for the adjacent vertex distinguishing acyclic edge chromatic number of a graph

A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges incident to υ, where uυ ∈ E(G). The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by χ′ _aa (G), is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. In this paper we prove that if G(V, E) is a graph with no isolated edges, then χ′ _aa (G) ≤ 32Δ. Supported by the Natural Science Foundation of Gansu Province (3ZS051-A25-025)     

Total Colorings Of Degenerate Graphs

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. A graph G is s-degenerate for a positive integer s if G can be reduced to a trivial graph by successive removal of vertices with degree ≤s. We prove that an s-degenerate graph G has a total coloring with Δ+1 colors if the maximum degree Δ of G is sufficiently large, say Δ≥4s+3. Our proof yields an efficient algorithm to find such a total coloring. We also give a lineartime algorithm to find a total coloring of a graph G with the minimum number of colors if G is a partial k-tree, that is, the tree-width of G is bounded by a fixed integer k.     

Super Connectivity and Super Edge Connectivity of the Mycielskian of a Graph

Mycielski introduced a new graph transformation μ(G) for graph G, which is called the Mycielskian of G. A graph G is super connected or simply super-κ (resp. super edge connected or super-λ), if every minimum vertex cut (resp. minimum edge cut) isolates a vertex of G. In this paper, we show that for a connected graph G with |V(G)| ≥ 2, μ(G) is super-κ if and only if δ(G) < 2κ(G), and μ(G) is super-λ if and only if G\ncong K₂{G\ncong K_2}.     

New Bounds on Crossing Numbers

The crossing number , cr(G) , of a graph G is the least number of crossing points in any drawing of G in the plane. Denote by κ(n,e) the minimum of cr(G) taken over all graphs with n vertices and at least e edges. We prove a conjecture of Erdos os and Guy by showing that κ(n,e)n ² /e ³ tends to a positive constant as n→∈fty and n l e l n ² . Similar results hold for graph drawings on any other surface of fixed genus. We prove better bounds for graphs satisfying some monotone properties. In particular, we show that if G is a graph with n vertices and e≥ 4n edges, which does not contain a cycle of length four (resp. six ), then its crossing number is at least ce ⁴ /n ³ (resp. ce ⁵ /n ⁴ ), where c>0 is a suitable constant. These results cannot be improved, apart from the value of the constant. This settles a question of Simonovits. Received January 27, 1999, and in revised form March 23, 1999.     

Boxicity of Circular Arc Graphs

A k-dimensional box is a Cartesian product R ₁ × · · · × R _k where each R _i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. That is, two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. We show that if G is a circular arc graph which admits a circular arc representation in which no arc has length at least p(\fraca-1a){\pi(\frac{\alpha-1}{\alpha})} for some a ? \mathbbN _{3 2}{\alpha\in\mathbb{N}_{\geq 2}}, then box(G) ≤ α (Here the arcs are considered with respect to a unit circle). From this result we show that if G has maximum degree D < ?\fracn(a-1)2a?{\Delta < \lfloor{\frac{n(\alpha-1)}{2\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha \in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. We also demonstrate a graph having box(G) > α but with D = n\frac(a-1)2a+ \fracn2a(a+1)+(a+2){\Delta=n\frac{(\alpha-1)}{2\alpha}+ \frac{n}{2\alpha(\alpha+1)}+(\alpha+2)}. For a proper circular arc graph G, we show that if D < ?\fracn(a-1)a?{\Delta < \lfloor{\frac{n(\alpha-1)}{\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha\in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. Let r be the cardinality of the minimum overlap set, i.e. the minimum number of arcs passing through any point on the circle, with respect to some circular arc representation of G. We show that for any circular arc graph G, box(G) ≤ r + 1 and this bound is tight. We show that if G admits a circular arc representation in which no family of k ≤ 3 arcs covers the circle, then box(G) ≤ 3 and if G admits a circular arc representation in which no family of k ≤ 4 arcs covers the circle, then box(G) ≤ 2. We also show that both these bounds are tight.     

An <Emphasis Type="Italic">s</Emphasis>-Hamiltonian Line Graph Problem

For an integer k > 0, a graph G is k-triangular if every edge of G lies in at least k distinct 3-cycles of G. In (J Graph Theory 11:399–407 (1987)), Broersma and Veldman proposed an open problem: for a given positive integer k, determine the value s for which the statement “Let G be a k-triangular graph. Then L(G), the line graph of G, is s-hamiltonian if and only L(G) is (s + 2)-connected” is valid. Broersma and Veldman proved in 1987 that the statement above holds for 0 ≤ s ≤ k and asked, specifically, if the statement holds when s = 2k. In this paper, we prove that the statement above holds for 0 ≤ s ≤ max{2k, 6k − 16}.     

On a graph property generalizing planarity and flatness

We introduce a topological graph parameter σ(G), defined for any graph G. This parameter characterizes subgraphs of paths, outerplanar graphs, planar graphs, and graphs that have a flat embedding as those graphs G with σ(G)≤1,2,3, and 4, respectively. Among several other theorems, we show that if H is a minor of G, then σ(H)≤σ(G), that σ(K _n )=n−1, and that if H is the suspension of G, then σ(H)=σ(G)+1. Furthermore, we show that μ(G)≤σ(G) + 2 for each graph G. Here μ(G) is the graph parameter introduced by Colin de Verdière in [2].     

Entropy,Periodicity, and Graphs with Zero Euler Characteristic

Let G be a graph which contains exactly one simple closed curve. We prove that a continuous map f : G → G has zero topological entropy if and only if there exist at most k ≤ |(Edg(G) End(G) 3)/2] different odd numbers n1,...,nk such that Per(f) is contained in ∪i=1^k ∪j=0^∞ ni2^j, where Edg(G) is the number of edges of G and End(G) is the number of end points of G.     

The Entire Coloring of Series-Parallel Graphs

The entire chromatic number X_(vef)(G) of a plane graph G is the minimal number of colors needed for coloring vertices, edges and faces of G such that no two adjacent or incident elements are of the same color. Let G be a series-parallel plane graph, that is, a plane graph which contains no subgraphs homeomorphic to K_(4-) It is proved in this paper that X_(vef)(G)≤max{8, △(G) 2} and X_(vef)(G)=△ 1 if G is 2-connected and △(G)≥6.     

Some results on distance two labelling of outerplanar graphs

Let G be an outerplanar graph with maximum degree △. Let χ（G^2） and A（G） denote the chromatic number of the square and the L（2, 1）-labelling number of G, respectively. In this paper we prove the following results： （1） χ（G^2） = 7 if △= 6; （2） λ（G） ≤ △ ＋5 if △ ≥ 4, and ）,（G）≤ 7 if △ = 3; and （3） there is an outerplanar graph G with △ = 4 such that ）λ（G） = 7. These improve some known results on the distance two labelling of outerplanar graphs.     

Folding Wheels and Fans

 If two non-adjacent vertices of a connected graph that have a common neighbor are identified and the resulting multiple edges are reduced to simple edges, then we obtain another graph of order one less than that of the original graph. This process can be repeated until the resulting graph is complete. We say that we have folded the graph onto complete graph. This process of folding a connected graph G onto a complete graph induces in a very natural way a partition of the vertex-set of G. We denote by F(G) the set of all complete graphs onto which G can be folded. We show here that if p and q are the largest and smallest orders, respectively, of the complete graph in F(W _n ) or F(F _n ), then K _s is in F(W _n ) or F(F _n ) for each s, q≤s≤p. Lastly, we shall also determine the exact values of p and q. Received: October, 2001 Final version received: June 26, 2002     

A Sharp Upper Bound for the Number of Spanning Trees of a Graph

Let G = (V,E) be a simple graph with n vertices, e edges and d₁ be the highest degree. Further let λ_i, i = 1,2,...,n be the non-increasing eigenvalues of the Laplacian matrix of the graph G. In this paper, we obtain the following result: For connected graph G, λ₂ = λ₃ = ... =  λ_n-1 if and only if G is a complete graph or a star graph or a (d₁,d₁) complete bipartite graph. Also we establish the following upper bound for the number of spanning trees of G on n, e and d₁ only: