On bipartite graphs with minimal energy

The energy of a graph is the sum of the absolute values of the eigenvalues of the graph. In a paper [G. Caporossi, D. Cvetkovi, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs. 2. Finding graphs with external energy, J. Chem. Inf. Comput. Sci. 39 (1999) 984-996] Caporossi et al. conjectured that among all connected graphs G with n≥6 vertices and n−1≤m≤2(n−2) edges, the graphs with minimum energy are the star S_n with m−n+1 additional edges all connected to the same vertices for m≤n+⌊(n−7)/2⌋, and the bipartite graph with two vertices on one side, one of which is connected to all vertices on the other side, otherwise. The conjecture is proved to be true for m=n−1,2(n−2) in the same paper by Caporossi et al. themselves, and for m=n by Hou in [Y. Hou, Unicyclic graphs with minimal energy, J. Math. Chem. 29 (2001) 163-168]. In this paper, we give a complete solution for the second part of the conjecture on bipartite graphs. Moreover, we determine the graph with the second-minimal energy in all connected bipartite graphs with n vertices and edges.     

Counting substructures I: Color critical graphs

Let F be a graph which contains an edge whose deletion reduces its chromatic number. We prove tight bounds on the number of copies of F in a graph with a prescribed number of vertices and edges. Our results extend those of Simonovits (1968) [8], who proved that there is one copy of F, and of Rademacher, Erd?s (1962) [1] and [2] and Lovász and Simonovits (1983) [4], who proved similar counting results when F is a complete graph.One of the simplest cases of our theorem is the following new result. There is an absolute positive constant c such that if n is sufficiently large and 1?q<cn, then every n vertex graph with ⌊n²/4⌋+q edges contains at least

     

Hamiltonian path saturated graphs with small size

A graph G is said to be hamiltonian path saturated (HPS for short), if G has no hamiltonian path but any addition of a new edge in G creates a hamiltonian path in G. It is known that an HPS graph of order n has size at most and, for n?6, the only HPS graph of order n and size is K_n-1∪K₁. Denote by sat(n,HP) the minimum size of an HPS graph of order n. We prove that sat(n,HP)?⌊(3n-1)/2⌋-2. Using some properties of Isaacs’ snarks we give, for every n?54, an HPS graph G_n of order n and size ⌊(3n-1)/2⌋. This proves sat(n,HP)?⌊(3n-1)/2⌋ for n?54. We also consider m-path cover saturated graphs and P_m-saturated graphs with small size.     

The Erdös-Sós conjecture for spiders

A classical result on extremal graph theory is the Erdös-Gallai theorem: if a graph on n vertices has more than edges, then it contains a path of k edges. Motivated by the result, Erdös and Sós conjectured that under the same condition, the graph should contain every tree of k edges. A spider is a rooted tree in which each vertex has degree one or two, except for the root. A leg of a spider is a path from the root to a vertex of degree one. Thus, a path is a spider of 1 or 2 legs. From the motivation, it is natural to consider spiders of 3 legs. In this paper, we prove that if a graph on n vertices has more than edges, then it contains every k-edge spider of 3 legs, and also, every k-edge spider with no leg of length more than 4, which strengthens a result of Wo?niak on spiders of diameter at most 4.     

Decomposing oriented graphs into transitive tournaments

For an oriented graph G with n vertices, let f(G) denote the minimum number of transitive subtournaments that decompose G. We prove several results on f(G). In particular, if G is a tournament then and there are tournaments for which f(G)>n²/3000. For general G we prove that f(G)?⌊n²/3⌋ and this is tight. Some related parameters are also considered.     

A circular embedding of a graph in Euclidean 3-space

A spatial embedding of a graph G is an embedding of G into the 3-dimensional Euclidean space . J.H. Conway and C.McA. Gordon proved that every spatial embedding of the complete graph on 7 vertices contains a nontrivial knot. A linear spatial embedding of a graph is an embedding which maps each edge to a single straight line segment. In this paper, we construct a linear spatial embedding of the complete graph on 2n−1 (or 2n) vertices which contains the torus knot T(2n−5,2) (n4). A circular spatial embedding of a graph is an embedding which maps each edge to a round arc. We define the circular number of a knot as the minimal number of round arcs in among such embeddings of the knot. We show that a knot has circular number 3 if and only if the knot is a trefoil knot, and the figure-eight knot has circular number 4.     

Noncrossing Hamiltonian paths in geometric graphs

A geometric graph is a graph embedded in the plane in such a way that vertices correspond to points in general position and edges correspond to segments connecting the appropriate points. A noncrossing Hamiltonian path in a geometric graph is a Hamiltonian path which does not contain any intersecting pair of edges. In the paper, we study a problem asked by Micha Perles: determine the largest number h(n) such that when we remove any set of h(n) edges from any complete geometric graph on n vertices, the resulting graph still has a noncrossing Hamiltonian path. We prove that . We also establish several results related to special classes of geometric graphs. Let h₁(n) denote the largest number such that when we remove edges of an arbitrary complete subgraph of size at most h₁(n) from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We prove that . Let h₂(n) denote the largest number such that when we remove an arbitrary star with at most h₂(n) edges from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We show that h₂(n)=⌈n/2⌉-1. Further we prove that when we remove any matching from a complete geometric graph the resulting graph will have a noncrossing Hamiltonian path.     

Consecutive magic graphs

Let G be a graph of order n and size e. A vertex-magic total labeling is an assignment of the integers 1,2,…,n+e to the vertices and the edges of G, so that at each vertex, the vertex label and the labels on the edges incident at that vertex, add to a fixed constant, called the magic number of G. Such a labeling is a-vertex consecutive magic if the set of the labels of the vertices is {a+1,a+2,…,a+n}, and is b-edge consecutive magic if the set of labels of the edges is {b+1,b+2,…,b+e}. In this paper we prove that if an a-vertex consecutive magic graph has isolated vertices then the order and the size satisfy (n-1)²+n²=(2e+1)². Moreover, we show that every tree with even order is not a-vertex consecutive magic and, if a tree of odd order is a-vertex consecutive then a=n-1. Furthermore, we show that every a-vertex consecutive magic graph has minimum degree at least two if a=0, or both and 2a?e, and the minimum degree is at least three if both and 2a?e. Finally, we state analogous results for b-edge consecutive magic graphs.     

The intersection of all maximum stable sets of a tree and its pendant vertices

A stable set in a graph G is a set of mutually non-adjacent vertices, α(G) is the size of a maximum stable set of G, and is the intersection of all its maximum stable sets. It is known that if G is a connected graph of order n≥2 with 2α(G)>n, then , [V.E. Levit, E. Mandrescu, Combinatorial properties of the family of maximum stable sets of a graph, Discrete Applied Mathematics 117 (2002) 149-161; E. Boros, M.C. Golumbic, V.E. Levit, On the number of vertices belonging to all maximum stable sets of a graph, Discrete Applied Mathematics 124 (2002) 17-25]. When we restrict ourselves to the class of trees, we add some structural properties to this statement. Our main finding is the theorem claiming that if T is a tree of order n≥2, with 2α(T)>n, then at least two pendant vertices an even distance apart belong to .     

On the spectral radii and the signless Laplacian spectral radii of c-cyclic graphs with fixed maximum degree

If G is a connected undirected simple graph on n vertices and n+c-1 edges, then G is called a c-cyclic graph. Specially, G is called a tricyclic graph if c=3. Let Δ(G) be the maximum degree of G. In this paper, we determine the structural characterizations of the c-cyclic graphs, which have the maximum spectral radii (resp. signless Laplacian spectral radii) in the class of c-cyclic graphs on n vertices with fixed maximum degree . Moreover, we prove that the spectral radius of a tricyclic graph G strictly increases with its maximum degree when , and identify the first six largest spectral radii and the corresponding graphs in the class of tricyclic graphs on n vertices.     

The edge-Wiener index of a graph

If G is a connected graph, then the distance between two edges is, by definition, the distance between the corresponding vertices of the line graph of G. The edge-Wiener index W_e of G is then equal to the sum of distances between all pairs of edges of G. We give bounds on W_e in terms of order and size. In particular we prove the asymptotically sharp upper bound for graphs of order n.     

The Laplacian spectral radius of some bipartite graphs

In this paper, we study the largest Laplacian spectral radius of the bipartite graphs with n vertices and k cut edges and the bicyclic bipartite graphs, respectively. Identifying the center of a star K_1,k and one vertex of degree n of K_m,n, we denote by the resulting graph. We show that the graph (1?k?n-4) is the unique graph with the largest Laplacian spectral radius among the bipartite graphs with n vertices and k cut edges, and (n?7) is the unique graph with the largest Laplacian spectral radius among all the bicyclic bipartite graphs.     

Linear coloring of planar graphs with large girth

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number of the graph G is the smallest number of colors in a linear coloring of G. In this paper we prove that every planar graph G with girth g and maximum degree Δ has if G satisfies one of the following four conditions: (1) g≥13 and Δ≥3; (2) g≥11 and Δ≥5; (3) g≥9 and Δ≥7; (4) g≥7 and Δ≥13. Moreover, we give better upper bounds of linear chromatic number for planar graphs with girth 5 or 6.     

Graphs with many r-cliques have large complete r-partite subgraphs

Let r2 and c>0. Every graph on n vertices with at least cn^rcliques on r vertices contains a complete r-partite subgraphwith r–1 parts of size c^rlog n and one part of size greaterthan n^1–cr–1. This result implies a quantitativeform of the Erdös–Stone theorem.     

The hamiltonian index of a 2-connected graph

Let G be a graph. Then the hamiltonian index h(G) of G is the smallest number of iterations of line graph operator that yield a hamiltonian graph. In this paper we show that for every 2-connected simple graph G that is not isomorphic to the graph obtained from a dipole with three parallel edges by replacing every edge by a path of length l≥3. We also show that for any two 2-connected nonhamiltonian graphs G and with at least 74 vertices. The upper bounds are all sharp.     

Graph designs for the eight-edge five-vertex graphs

The existence of graph designs for the two nonisomorphic graphs on five vertices and eight edges is determined in the case of index one, with three possible exceptions in total. It is established that for the unique graph with vertex sequence (3, 3, 3, 3, 4), a graph design of order n exists exactly when and n≠16, with the possible exception of n=48. For the unique graph with vertex sequence (2,3,3,4,4), a graph design of order n exists exactly when , with the possible exceptions of n∈{32,48}.     

Tutte’s 5-flow conjecture for highly cyclically connected cubic graphs

In 1954, Tutte conjectured that every bridgeless graph has a nowhere-zero 5-flow. Let ω(G) be the minimum number of odd cycles in a 2-factor of a bridgeless cubic graph G. Tutte’s conjecture is equivalent to its restriction to cubic graphs with ω≥2. We show that if a cubic graph G has no edge cut with fewer than edges that separates two odd cycles of a minimum 2-factor of G, then G has a nowhere-zero 5-flow. This implies that if a cubic graph G is cyclically n-edge connected and , then G has a nowhere-zero 5-flow.     

Transversal structures on triangulations: A combinatorial study and straight-line drawings

This article focuses on a combinatorial structure specific to triangulated plane graphs with quadrangular outer face and no separating triangle, which are called irreducible triangulations. The structure has been introduced by Xin He under the name of regular edge-labelling and consists of two bipolar orientations that are transversal. For this reason, the terminology used here is that of transversal structures. The main results obtained in the article are a bijection between irreducible triangulations and ternary trees, and a straight-line drawing algorithm for irreducible triangulations. For a random irreducible triangulation with n vertices, the grid size of the drawing is asymptotically with high probability 11n/27×11n/27 up to an additive error of . In contrast, the best previously known algorithm for these triangulations only guarantees a grid size (⌈n/2⌉−1)×⌊n/2⌋.