On minors of graphs with at least 3n −4 edges

A point disconnecting set S of a graph G is a nontrivial m-separator, where m = |S|, if the connected components of G - S can be partitioned into two subgraphs, each of which has at least two points. A 3-connected graph is quasi 4-connected if it has no nontrivial 3-separators. Suppose G is a graph having n ≥ 6 points. We prove three results: (1) If G is quasi 4-connected with at least 3n - 4 edges, then the graph K^?₁, obtained from K₆ by deleting an edge, is a minor of G. (2) If G has at least 3n - 4 edges then either K^?₆ or the graph obtained by pasting two disjoint copies of K₅ together along a triangle is a minor of G. (3) If the minimum degree of G is at least 6, then K^?₆ is a minor of G. © 1993 John Wiley & Sons, Inc.     

Subdivisions of K5 in Graphs Embedded on Surfaces With Face‐Width at Least 5

We prove that if G is a 5‐connected graph embedded on a surface Σ (other than the sphere) with face‐width at least 5, then G contains a subdivision of K₅. This is a special case of a conjecture of P. Seymour, that every 5‐connected nonplanar graph contains a subdivision of K₅. Moreover, we prove that if G is 6‐connected and embedded with face‐width at least 5, then for every v ∈ V(G), G contains a subdivision of K₅ whose branch vertices are v and four neighbors of v.     

Prism‐hamiltonicity of triangulations

The prism over a graph G is the Cartesian product G □ K₂ of G with the complete graph K₂. If the prism over G is hamiltonian, we say that G is prism‐hamiltonian. We prove that triangulations of the plane, projective plane, torus, and Klein bottle are prism‐hamiltonian. We additionally show that every 4‐connected triangulation of a surface with sufficiently large representativity is prism‐hamiltonian, and that every 3‐connected planar bipartite graph is prism‐hamiltonian. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 181–197, 2008     

Large P4-free graphs with bounded degree

Let ex * (D; H) denote the maximum number of edges in a connected graph with maximum degree D and no induced subgraph isomorphic to H. We prove that this is finite only when H is a disjoint union of paths,m in which case we provide crude upper and lower bounds. When H is the four-vertex path P₄, we prove that the complete bipartite graph K_D,D is the unique extremal graph. Furthermore, if G is a connected P₄-free graph with maximum degree D and clique number ω, then G has at most D² ? D(ω ? 2)/2 edges. © 1993 John Wiley & Sons, Inc.     

On the toroidal thickness of graphs

The toroidal thickness t₁(G) of a graph G is the minimum value of k such that G is the union of k graphs each of which is embeddable on a torus. We find t₁(G_m), where G_m is the graph obtained from the complete graph K_m by removing a Hamiltonian cycle, and we show that t₁(K_n(3)) = [1/2n] for many values of n. The method of approach involves the construction of sets of triples related to Skolem triples.     

Undirected power graphs of semigroups

The undirected power graph G(S) of a semigroup S is an undirected graph whose vertex set is S and two vertices a,b∈S are adjacent if and only if a≠b and a ^m =b or b ^m =a for some positive integer m. In this paper we characterize the class of semigroups S for which G(S) is connected or complete. As a consequence we prove that G(G) is connected for any finite group G and G(G) is complete if and only if G is a cyclic group of order 1 or p ^m . Particular attention is given to the multiplicative semigroup ℤ _n and its subgroup U _n , where G(U _n ) is a major component of G(ℤ _n ). It is proved that G(U _n ) is complete if and only if n=1,2,4,p or 2p, where p is a Fermat prime. In general, we compute the number of edges of G(G) for a finite group G and apply this result to determine the values of n for which G(U _n ) is planar. Finally we show that for any cyclic group of order greater than or equal to 3, G(G) is Hamiltonian and list some values of n for which G(U _n ) has no Hamiltonian cycle.     

On Hamiltonian-connected regular graphs

In this paper it is shown that any m-regular graph of order 2m (m ≧ 3), not isomorphic to K_m,m, or of order 2m + 1 (m even, m ≧ 4), is Hamiltonian connected, which extends a previous result of Nash-Williams. As a corollary, it is derived that any such graph contains atleast m Hamiltonian cycles for odd m and atleast 1/2m Hamiltonian cycles for even m.     

Trivalent 2-Arc Transitive Graphs of Type {G^1_2} are Near Polygonal

A connected graph Σ of girth at least four is called a near n-gonal graph with respect to E, where n ≥  4 is an integer, if E is a set of n-cycles of Σ such that every path of length two is contained in a unique member of E. It is well known that connected trivalent symmetric graphs can be classified into seven types. In this note we prove that every connected trivalent G-symmetric graph S 1 K₄{\Sigma \neq K_4} of type G¹₂{G^1_2} is a near polygonal graph with respect to two G-orbits on cycles of Σ. Moreover, we give an algorithm for constructing the unique cycle in each of these G-orbits containing a given path of length two.     

Graph powers and k-ordered Hamiltonicity

It is known that if G is a connected simple graph, then G³ is Hamiltonian (in fact, Hamilton-connected). A simple graph is k-ordered Hamiltonian if for any sequence v₁, v₂,…,v_k of k vertices there is a Hamiltonian cycle containing these vertices in the given order. In this paper, we prove that if k?4, then G^⌊3k/2⌋-2 is k-ordered Hamiltonian for every connected graph G on at least k vertices. By considering the case of the path graph P_n, we show that this result is sharp. We also give a lower bound on the power of the cycle C_n that guarantees k-ordered Hamiltonicity.     

Decompositions of complete graphs and complete bipartite graphs into isomorphic supersubdivision graphs

A graph H is called a supersubdivison of a graph G if H is obtained from G by replacing every edge uv of G by a complete bipartite graph K_2,m (m may vary for each edge) by identifying u and v with the two vertices in K_2,m that form one of the two partite sets. We denote the set of all such supersubdivision graphs by SS(G). Then, we prove the following results.

1. Each non-trivial connected graph G and each supersubdivision graph HSS(G) admits an α-valuation. Consequently, due to the results of Rosa (in: Theory of Graphs, International Symposium, Rome, July 1966, Gordon and Breach, New York, Dunod, Paris, 1967, p. 349) and El-Zanati and Vanden Eynden (J. Combin. Designs 4 (1996) 51), it follows that complete graphs K_2cq+1 and complete bipartite graphs K_mq,nq can be decomposed into edge disjoined copies of HSS(G), for all positive integers m,n and c, where q=|E(H)|.

2. Each connected graph G and each supersubdivision graph in SS(G) is strongly n-elegant, where n=|V(G)| and felicitous.

3. Each supersubdivision graph in EASS(G), the set of all even arbitrary supersubdivision graphs of any graph G, is cordial.

Further, we discuss a related open problem.     

K4−‐factor in a graph

Let G be a graph of order 4k and let δ(G) denote the minimum degree of G. Let F be a given connected graph. Suppose that |V(G)| is a multiple of |V(F)|. A spanning subgraph of G is called an F‐factor if its components are all isomorphic to F. In this paper, we prove that if δ(G)≥5/2k, then G contains a K₄^?‐factor (K₄^? is the graph obtained from K₄ by deleting just one edge). The condition on the minimum degree is best possible in a sense. In addition, the proof can be made algorithmic. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 111–128, 2002     

Antimagic labelling of vertex weighted graphs

Suppose G is a graph, k is a non‐negative integer. We say G is k‐antimagic if there is an injection f: E→{1, 2, …, |E| + k} such that for any two distinct vertices u and v, . We say G is weighted‐k‐antimagic if for any vertex weight function w: V→?, there is an injection f: E→{1, 2, …, |E| + k} such that for any two distinct vertices u and v, . A well‐known conjecture asserts that every connected graph G≠K₂ is 0‐antimagic. On the other hand, there are connected graphs G≠K₂ which are not weighted‐1‐antimagic. It is unknown whether every connected graph G≠K₂ is weighted‐2‐antimagic. In this paper, we prove that if G has a universal vertex, then G is weighted‐2‐antimagic. If G has a prime number of vertices and has a Hamiltonian path, then G is weighted‐1‐antimagic. We also prove that every connected graph G≠K₂ on n vertices is weighted‐ ?3n/2?‐antimagic. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

The spanning subgraphs of eulerian graphs

It is shown that a connected graph G spans an eulerian graph if and only if G is not spanned by an odd complete bigraph K(2_m + 1, 2n + 1). A disconnected graph spans an eulerian graph if and only if it is not the union of the trivial graph with a complete graph of odd order. Exact formulas are obtained for the number of lines which must be added to such graphs in order to get eulerian graphs.     

On antimagic directed graphs

An antimagic labeling of an undirected graph G with n vertices and m edges is a bijection from the set of edges of G to the integers {1, …, m} such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labeling. In (N. Hartsfield and G. Ringel, Pearls in Graph Theory, Academic Press, Boston, 1990, pp. 108–109), Hartsfield and Ringel conjectured that every simple connected graph, other than K₂, is antimagic. Despite considerable effort in recent years, this conjecture is still open. In this article we study a natural variation; namely, we consider antimagic labelings of directed graphs. In particular, we prove that every directed graph whose underlying undirected graph is “dense” is antimagic, and that almost every undirected d‐regular graph admits an orientation which is antimagic. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 219–232, 2010     

An application of the combinatorial Nullstellensatz to a graph labelling problem

An antimagic labelling of a graph G with m edges and n vertices is a bijection from the set of edges of G to the set of integers {1,…,m}, such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labelling. In N. Hartsfield and G. Ringle, Pearls in Graph Theory, Academic Press, Inc., Boston, 1990, Ringel has conjectured that every simple connected graph, other than K₂, is antimagic. In this article, we prove a special case of this conjecture. Namely, we prove that if G is a graph on n=p^k vertices, where p is an odd prime and k is a positive integer that admits a C_p‐factor, then it is antimagic. The case p=3 was proved in D. Hefetz, J Graph Theory 50 (2005), 263–272. Our main tool is the combinatorial Nullstellensatz [N. Alon, Combin Probab Comput 8(1–2) (1999), 7–29]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 70–82, 2010.     

Distinguishing Cartesian powers of graphs

The distinguishing number D(G) of a graph is the least integer d such that there is a d‐labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G ≠ K₂, K₃ with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 ( 1 ), #N17] on powers of prime graphs, and results of Klav?ar and Zhu [Eu J Combin, to appear]. More generally, we also prove that d(G □ H) = 2 if G and H are relatively prime and |H| ≤ |G| < 2^|H| ? |H|. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 250–260, 2006     

Orientable imbedding of line graphs

In this paper we compute the orientable genus of the line graph of a graph G, when G is a tree and a 2-edge connected graph, all the vertices of which have their degrees equal to 2, 3, 6, or 11 modulo 12, and either G can be imbedded with triangular faces only or G is a bipartite graph which can be imbedded with squares only as faces. In the other cases, we give an upper bound of the genus of line graphs. In this way, we solve the question of the Hamiltonian genus of the complete graph K_n, for every n ≥ 3.     

Dirac type condition and Hamiltonian-connected graphs

Abstract

In 1952 Dirac introduced the Dirac type condition and proved that if G is a connected graph of order n ≥ 3 such that δ(G) ≥ n/2, then G is Hamiltonian. In this paper we consider Hamiltonian-connectedness, which extends the Hamiltonian graphs and prove that if G is a connected graph of order n ≥ 3 such that δ(G) ≥ (n ?1)/2, then G is Hamiltonian-connected or G belongs to five families of well-structured graphs. Thus, the condition and the result generalize the above condition and results of Dirac, respectively.     

Every 3-connected,locally connected,claw-free graph is Hamilton-connected

A graph G is locally connected if the subgraph induced by the neighbourhood of each vertex is connected. We prove that a locally connected graph G of order p ≥ 4, containing no induced subgraph isomorphic to K_1,3, is Hamilton-connected if and only if G is 3-connected. © 1996 John Wiley & Sons, Inc.     

Line graphs of bipartite graphs with Hamiltonian paths

It is shown that, if t is an integer ≥3 and not equal to 7 or 8, then there is a unique maximal graph having the path P_t as a star complement for the eigenvalue ?2. The maximal graph is the line graph of K_m,m if t = 2m?1, and of K_m,m+1 if t = 2m. This result yields a characterization of L(G ) when G is a (t + 1)‐vertex bipartite graph with a Hamiltonian path. The graphs with star complement P_r ∪ P_s or P_r ∪ C_s for ?2 are also determined. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 137–149, 2003