On chaotic graphs and applications in physics and biology

El Naschie’s ε^∞ theory in Quantum space time is given and discussed geometrically and topologically as a category of fuzzy spaces, these fuzzy categories in which lines are fuzzy fractal lines. In this paper, we represent the chaotic graphs as many fuzzy fractal lines up to ∞. We will describe them by chaotic matrices. Many fuzzy systems (chaotic systems) are described and applied in [8], [9], [10], [11], [12]. This article introduces some operations on the chaotic graphs such as the union and the intersection; also both of the chaotic incidence matrices and the chaotic adjacency matrices representing the chaotic graphs induced from these operations will be studied. Theorems governing these studies are obtained. Some applications on chaotic graphs are given [18], [19], [20], [21].     

Improper colouring of (random) unit disk graphs

For any graph G, the k-improper chromatic numberχ^k(G) is the smallest number of colours used in a colouring of G such that each colour class induces a subgraph of maximum degree k. We investigate χ^k for unit disk graphs and random unit disk graphs to generalise results of McDiarmid and Reed [Colouring proximity graphs in the plane, Discrete Math. 199(1-3) (1999) 123-137], McDiarmid [Random channel assignment in the plane, Random Structures Algorithms 22(2) (2003) 187-212], and McDiarmid and Müller [On the chromatic number of random geometric graphs, submitted for publication].     

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.     

Lightness of digraphs in surfaces and directed game chromatic number

The lightness of a digraph is the minimum arc value, where the value of an arc is the maximum of the in-degrees of its terminal vertices. We determine upper bounds for the lightness of simple digraphs with minimum in-degree at least 1 (resp., graphs with minimum degree at least 2) and a given girth k, and without 4-cycles, which can be embedded in a surface S. (Graphs are considered as digraphs each arc having a parallel arc of opposite direction.) In case k≥5, these bounds are tight for surfaces of nonnegative Euler characteristics. This generalizes results of He et al. [W. He, X. Hou, K.-W. Lih, J. Shao, W. Wang, X. Zhu, Edge-partitions of planar graphs and their game coloring numbers, J. Graph Theory 41 (2002) 307-317] concerning the lightness of planar graphs. From these bounds we obtain directly new bounds for the game colouring number, and thus for the game chromatic number of (di)graphs with girth k and without 4-cycles embeddable in S. The game chromatic resp. game colouring number were introduced by Bodlaender [H.L. Bodlaender, On the complexity of some coloring games, Int. J. Found. Comput. Sci. 2 (1991) 133-147] resp. Zhu [X. Zhu, The game coloring number of planar graphs, J. Combin. Theory B 75 (1999) 245-258] for graphs. We generalize these notions to arbitrary digraphs. We prove that the game colouring number of a directed simple forest is at most 3.     

Hamiltonicity in vertex envelopes of plane cubic graphs

In this paper we study a graph operation which produces what we call the “vertex envelope” G^∗_V from a graph G. We apply it to plane cubic graphs and investigate the hamiltonicity of the resulting graphs, which are also cubic. To this end, we prove a result giving a necessary and sufficient condition for the existence of hamiltonian cycles in the vertex envelopes of plane cubic graphs. We then use these conditions to identify graphs or classes of graphs whose vertex envelopes are either all hamiltonian or all non-hamiltonian, paying special attention to bipartite graphs. We also show that deciding if a vertex envelope is hamiltonian is NP-complete, and we provide a polynomial algorithm for deciding if a given cubic plane graph is a vertex envelope.     

Almost arcwise connected continua without dense arc components

A continuum M is almost arcwise connected if each pair of nonempty open subsets of M can be joined by an arc in M. An almost arcwise connected plane continuum without a dense arc component can be defined by identifying pairs of endpoints of three copies of the Knaster indecomposable continuum that has two endpoints. In [7] K.R. Kellum gave this example and asked if every almost arcwise connected continuum without a dense arc component has uncountably many arc components. We answer Kellum's question by defining an almost arcwise connected plane continuum with only three arc components none of which are dense. A continuum M is almost Peano if for each finite collection $\text{C}$ of nonempty open subsets of M there is a Peano continuum in M that intersects each element of $\text{C}$. We define a hereditarily unicoherent almost Peano plane continuum that does not have a dense arc component. We prove that every almost arcwise connected planar λ-dendroid has exactly one dense arc component. It follows that every hereditarily unicoherent almost arcwise connected plane continuum without a dense arc component has uncountably many arc components. Using an example of J. Krasinkiewicz and P Minc [8], we define an almost Peano λ-dendroid that do not have a dense arc component. Using a theorem of J.B. Fugate and L. Mohler [3], we prove that every almost arcwise connected λ-dendroid without a dense arc component has uncountably many arc components. In Euclidean 3-space we define an almost Peano continuum with only countably many arc components no one of which is dense. It is not known if the plane contains a continuum with these properties.     

Paths through inverse limits

In Bani?, ?repnjak, Merhar and Milutinovi? (2010) [2] the authors proved that if a sequence of graphs of surjective upper semi-continuous set-valued functions fn:X→X² converges to the graph of a continuous single-valued function f:X→X, then the sequence of corresponding inverse limits obtained from fn converges to the inverse limit obtained from f. In this paper a more general result is presented in which surjectivity of fn is not required. The result is also generalized to the case of inverse sequences with non-constant sequences of bonding maps. Finally, these new theorems are applied to inverse limits with tent maps. Among other applications, it is shown that the inverse limits appearing in the Ingram conjecture (with a point added) form an arc.     

Convex drawings of hierarchical planar graphs and clustered planar graphs

In this paper, we present results on convex drawings of hierarchical graphs and clustered graphs. A convex drawing is a planar straight-line drawing of a plane graph, where every facial cycle is drawn as a convex polygon. Hierarchical graphs and clustered graphs are useful graph models with structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures.We first present the necessary and sufficient conditions for a hierarchical plane graph to admit a convex drawing. More specifically, we show that the necessary and sufficient conditions for a biconnected plane graph due to Thomassen [C. Thomassen, Plane representations of graphs, in: J.A. Bondy, U.S.R. Murty (Eds.), Progress in Graph Theory, Academic Press, 1984, pp. 43–69] remains valid for the case of a hierarchical plane graph. We then prove that every internally triconnected clustered plane graph with a completely connected clustering structure admits a “fully convex drawing,” a planar straight-line drawing such that both clusters and facial cycles are drawn as convex polygons. We also present algorithms to construct such convex drawings of hierarchical graphs and clustered graphs.     

A Center Transversal Theorem for Hyperplanes and Applications to Graph Drawing

Motivated by an open problem from graph drawing, we study several partitioning problems for line and hyperplane arrangements. We prove a ham-sandwich cut theorem: given two sets of n lines in ?², there is a line ? such that in both line sets, for both halfplanes delimited by ?, there are $\sqrt{n}$ lines which pairwise intersect in that halfplane, and this bound is tight; a centerpoint theorem: for any set of n lines there is a point such that for any halfplane containing that point there are $\sqrt{n/3}$ of the lines which pairwise intersect in that halfplane. We generalize those results in higher dimension and obtain a center transversal theorem, a same-type lemma, and a positive portion Erd?s–Szekeres theorem for hyperplane arrangements. This is done by formulating a generalization of the center transversal theorem which applies to set functions that are much more general than measures. Back to graph drawing (and in the plane), we completely solve the open problem that motivated our search: there is no set of n labeled lines that are universal for all n-vertex labeled planar graphs. In contrast, the main result by Pach and Toth (J. Graph Theory 46(1):39–47, 2004), has, as an easy consequence, that every set of n (unlabeled) lines is universal for all n-vertex (unlabeled) planar graphs.     

The condition on the stability of stationary lines in a curvature flow in the whole plane

The long time behavior of a curve in the whole plane moving by a curvature flow is studied. Studying the Cauchy problem, we deal with moving curves represented by entire graphs on the x-axis. Here the initial curves are given by bounded functions on the x-axis. It is proved that the solution converges uniformly to the solution of the Cauchy problem of the heat equation with the same initial value. The difference is of order O(t−1/2) as time goes to infinity. The proof is based on the decay estimates for the derivatives of the solution. By virtue of the stability results for the heat equation, our result gives the sufficient and necessary condition on the stability of constant solutions that represent stationary lines of the curvature flow in the whole plane.     

On the approximation of curves with polylines

The exact values of the estimation of the approximation error of parametrically defined curves by inscribed polylines in them-dimensional space R ^m for classes of functions defined by moduli of continuity are presented. The result is a sort of generalization of the results of B.N. Malozemov on the approximation of continuous functions with polylines. Also, the problem of finding the upper bounds of deviations of parametrically defined curves for this class is solved based on the assumption that these curves intersect at N (N ≥ 2) points of the partition of [0, L]. In the case of m = 2, from the obtained results follow the previous results on the approximation of plane curves with polylines in Euclidean, Hausdorff, and Hamming metrices.     

Dominating sets and domatic number of circular arc graphs

A dominating set of a graph G = (N,E) is a subset S of nodes such that every node is either in S or adjacent to a node which is in S. The domatic number of G is the size of a maximum cardinality partition of N into dominating sets. The problems of finding a minimum cardinality dominating set and the domatic number are both NP-complete even for special classes of graphs. In the present paper we give an O(n∣E∣) time algorithm that finds a minimum cardinality dominating set when G is a circular arc graph (intersection graph of arcs on a circle). The domatic number problem is solved in O(n² log n) time when G is a proper circular arc graph, and it is shown NP-complete for general circular arc graphs.     

Constructing Ramsey graphs from Boolean function representations

Explicit construction of Ramsey graphs or graphs with no large clique or independent set, has remained a challenging open problem for a long time. While Erdös’ probabilistic argument shows the existence of graphs on 2n vertices with no clique or independent set of size 2 ⁿ , the best explicit constructions achieve a far weaker bound. There is a connection between Ramsey graph constructions and polynomial representations of Boolean functions due to Grolmusz; a low degree representation for the OR function can be used to explicitly construct Ramsey graphs [17,18]. We generalize the above relation by proposing a new framework. We propose a new definition of OR representations: a pair of polynomials represent the OR function if the union of their zero sets contains all points in {0, 1} ⁿ except the origin. We give a simple construction of a Ramsey graph using such polynomials. Furthermore, we show that all the known algebraic constructions, ones to due to Frankl-Wilson [12], Grolmusz [18] and Alon [2] are captured by this framework; they can all be derived from various OR representations of degree O(√n) based on symmetric polynomials. Thus the barrier to better Ramsey constructions through such algebraic methods appears to be the construction of lower degree representations. Using new algebraic techniques, we show that better bounds cannot be obtained using symmetric polynomials.     

ON CLASSES OF REGULAR GRAPHS WITH CONSTANT METRIC DIMENSION

In this paper,we are dealing with the study of the metric dimension of some classes of regular graphs by considering a class of bridgeless cubic graphs called the flower snarks Jn,a class of cubic convex polytopes considering the open problem raised in [M.Imran et al.,families of plane graphs with constant metric dimension,Utilitas Math.,in press] and finally Harary graphs H 5,n by partially answering to an open problem proposed in [I.Javaid et al.,Families of regular graphs with constant metric dimension,Utilitas Math.,2012,88:43-57].We prove that these classes of regular graphs have constant metric dimension.     

Koszul duality in deformation quantization and Tamarkin's approach to Kontsevich formality

Let α be a quadratic Poisson bivector on a vector space V. Then one can also consider α as a quadratic Poisson bivector on the vector space V^∗[1]. Fixed a universal deformation quantization (prediction of some complex weights to all Kontsevich graphs [12]), we have deformation quantization of the both algebras S(V^∗) and Λ(V). These are graded quadratic algebras, and therefore Koszul algebras. We prove that for some universal deformation quantization, independent on α, these two algebras are Koszul dual. We characterize some deformation quantizations for which this theorem is true in the framework of the Tamarkin's theory [19].     

A note on class one graphs with maximum degree six

It is known that there are class two graphs with Δ=6 which can be embedded in a surface Σ with Euler characteristic χ(Σ)?0. However, it is unknown whether there are class two graphs on the projective plane or on the plane with Δ=6. In this paper, we prove that every graph with Δ=6 is class one if it can be embedded in a surface with Euler characteristic at least -3 and is C₃-free, or C₄-free or if it can be embedded in a surface with Euler characteristic at least -1 and is C₅-free. This generalizes Zhou's results in [G. Zhou, A note on graphs of class I, Discrete Math. 263 (2003) 339-345] on planar graphs.     

Boolean approach to planar embeddings of a graph

The purpose of this paper which is a sequel of “ Boolean planarity characterization of graphs ” [9] is to show the following results.

1. Both of the problems of testing the planarity of graphs and embedding a planar graph into the plane are equivalent to finding a spanning tree in another graph whose order and size are bounded by a linear function of the order and the size of the original graph, respectively.
2. The number of topologically non-equivalent planar embeddings of a Hamiltonian planar graphG is τ(G)=2 ^c(H)?1, wherec (H) is the number of the components of the graphH which is related toG.

     

A characterization of the minimalbasis of the torus

D. König asks the interesting question in [7] whether there are facts corresponding to the theorem of Kuratowski which apply to closed orientable or non-orientable surfaces of any genus. Since then this problem has been solved only for the projective plane ([2], [3], [8]). In order to demonstrate that König’s question can be affirmed we shall first prove, that every minimal graph of the minimal basis of all graphs which cannot be embedded into the orientable surface f of genusp has orientable genusp+1 and non-orientable genusq with 1≦q≦2p+2. Then let f be the torus. We shall derive a characterization of all minimal graphs of the minimal basis with the nonorientable genusq=1 which are not embeddable into the torus. There will be two very important graphs signed withX ₈ andX ₇ later. Furthermore 19 graphsG ₁,G ₂, ...,G ₁₉ of the minimal basisM(torus, >₄) will be specified. We shall prove that five of them have non-orientable genusq=1, ten of them have non-orientable genusq=2 and four of them non-orientable genusq=3. Then we shall point out a method of determining graphs of the minimal basisM(torus, >₄) which are embeddable into the projective plane. Using the possibilities of embedding into the projective plane the results of [2] and [3] are necessary. This method will be called saturation method. Using the minimal basisM(projective plane, >₄) of [3] we shall at last develop a method of determining all graphs ofM(torus, >₄) which have non-orientable genusq≧2. Applying this method we shall succeed in characterizing all minimal graphs which are not embeddable into the torus. The importance of the saturation method will be shown by determining another graphG ₂₀≠G ₁,G ₂, ...,G ₁₉ ofM(torus, >₄).