On spanning tree congestion of graphs

Let G be a connected graph and T be a spanning tree of G. For e∈E(T), the congestion of e is the number of edges in G connecting two components of T−e. The edge congestion ofGinT is the maximum congestion over all edges in T. The spanning tree congestion ofG is the minimum congestion of G in its spanning trees. In this paper, we show the spanning tree congestion for the complete k-partite graphs and the two-dimensional tori. We also address lower bounds of spanning tree congestion for the multi-dimensional grids and the hypercubes.     

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).     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory     

The independence number condition for the existence of a spanning f‐tree

Let G be a graph and f be a mapping from V(G) to the positive integers. A subgraph T of G is called an f‐tree if T forms a tree and d_T(x)≤f(x) for any x∈V(T). We propose a conjecture on the existence of a spanning f‐tree, and give a partial solution to it. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 173–184, 2010     

On low bound of degree sequences of spanning trees in K-edge-connected graphs

A graph G = (V, E) is k-edge-connected if for any subset E′ ⊆ E,|E′| < k, G − E′ is connected. A d_k-tree T of a connected graph G = (V, E) is a spanning tree satisfying that ∀v ∈ V, d_T(v) ≤ + α, where [·] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d_k-tree, and α = 1 for k = 2, α = 2 for k ≥ 3. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 87–95, 1998     

Finite Groups with Few Non-Abelian Subgroups

Let G be a finite group and τ(G) denote the number of conjugacy classes of all non-abelian subgroups of G. The symbol π(G) denotes the set of the prime divisors of |G|. In this paper, finite groups with τ(G) ≤ |π(G)| are classified completely. Furthermore, finite nonsolvable groups with τ(G) = |π(G)| +1 are determined.     

On connectivities of tree graphs

Let T(G) be the tree graph of a graph G with cycle rank r. Then κ(T(G)) ? m(G) ? r, where κ(T(G)) and m(G) denote the connectivity of T(G) and the length of a minimum cycle basis for G, respectively. Moreover, the lower bound of m(G) ? r is best possible.     

Infinite paths in planar graphs III, 1‐way infinite paths

An infinite graph is 2‐indivisible if the deletion of any finite set of vertices from the graph results in exactly one infinite component. Let G be a 4‐connected, 2‐indivisible, infinite, plane graph. It is known that G contains a spanning 1‐way infinite path. In this paper, we prove a stronger result by showing that, for any vertex x and any edge e on a facial cycle of G, there is a spanning 1‐way infinite path in G from x and through e. Results will be used in two forthcoming papers to establish a conjecture of Nash‐Williams. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Neighborhood unions and hamilton cycles

Let G be a graph on n vertices and N₂(G) denote the minimum size of N(u) ∪ N(v) taken over all pairs of independent vertices u, v of G. We show that if G is 3-connected and N₂(G) ? ½(n + 1), then G has a Hamilton cycle. We show further that if G is 2-connected and N₂(G) ? ½(n + 3), then either G has a Hamilton cycle or else G belongs to one of three families of exceptional graphs.     

A degree condition for spanning eulerian subgraphs

Let p ≥ 2 be a fixed integer. Let G be a simple and 2-edge-connected graph on n vertices, and let g be the girth of G. If d(u) + d(v) ≥ (2/(g ? 2))((n/p) ? 4 + g) holds whenever uv ? E(G), and if n is sufficiently large compared to p, then either G has a spanning eulerian subgraph or G can be contracted to a graph G₁ of order at most p without a spanning eulerian subgraph. Furthermore, we characterize the graphs that satisfy the conditions above such that G₁ has order p and does not have any spanning eulerian subgraph. © 1993 John Wiley & Sons, Inc.     

A characterization of panconnected graphs satisfying a local ore-type condition

It is well known that a graph G of order p ≥ 3 is Hamilton-connected if d(u) + d(v) ≥ p + 1 for each pair of nonadjacent vertices u and v. In this paper we consider connected graphs G of order at least 3 for which d(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| + 1 for any path uwv with uv ∉ E(G), where N(x) denote the neighborhood of a vertex x. We prove that a graph G satisfying this condition has the following properties: (a) For each pair of nonadjacent vertices x, y of G and for each integer k, d(x, y) ≤ k ≤ |V(G)| − 1, there is an x − y path of length k. (b) For each edge xy of G and for each integer k (excepting maybe one k η {3,4}) there is a cycle of length k containing xy. Consequently G is panconnected (and also edge pancyclic) if and only if each edge of G belongs to a triangle and a quadrangle. Our results imply some results of Williamson, Faudree, and Schelp. © 1996 John Wiley & Sons, Inc.     

A generalization of Plantholt's theorem

Let K denote the complete graph K_2n+1 with each edge replicated r times and let χ′(G) denote the chromatic index of a multigraph G. A multigraph G is critical if χ′(G) > χ′(G/e) for each edge e of G. Let S be a set of sn – 1 edges of K. We show that, for 0 < s ≦ r, G/S is critical and that χ′ (G/(S ∪{e})) = 2rn + r – s for all e ∈ E(G/S). Plantholt [M. Plantholt, The chromatic index of graphs with a spanning star. J. Graph Theory 5 (1981) 5–13] proved this result in the case when r = 1.     

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     

On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

An intermediate value theorem for graphs with given automorphism group

For a positive integer n and a finite group G, let the symbols e(G, n) and E(G, n) denote, respectively, the smallest and the greatest number of lines among all n-point graphs with automorphism group G. We say that the Intermediate Value Theorem (IVT) holds for G and n, if for each e satisfying e(G, n)≤e≤E(G, n), there exists an n-point graph with group G and e lines. The main result of this paper states that for every group G the IVT holds for all sufficiently large n. We also prove that the IVT holds for the identity group and all n, and exhibit examples of groups for which the IVT fails to hold for small values of n.     

Direct products of cyclic semigroups an unions of groups

We consider direct productsS×U_eεE G _e=S ₁×…×S _n × U_eεE G _e of non-group finite cyclic semigroupsS _i, 1 ≤i ≤n, and finite unions of finite groups U_eεE G _e We prove that if such a semigroup is isomorphic to another of the same form, sayT×U _fεF H _f =T ₁×…×U _fεF H _f , whereT _j are non-group cyclic semigroups, 1≤j≤l, and U _fεF H _f is a union of groups, thenS is isomorphic toT and U_eεE G _e is isomorphic to U_fεF H _f . We then determine when a finite semigroup has such a decomposition and show how the direct factors can be found.     

Set domination in graphs

Let G = (V, E) be a connected graph. A set D ? V is a set-dominating set (sd-set) if for every set T ? V ? D, there exists a nonempty set S ? D such that the subgraph 〈S ∪ T〉 induced by S ∪ T is connected. The set-domination number γ_s(G) of G is the minimum cardinality of a sd-set. In this paper we develop properties of this new parameter and relate it to some other known domination parameters.     

Various Forms of Generating Subsemigroups in Algebraic Monoids

Let M be an irreducible affine algebraic monoid over an algebraically closed field, G its unit group, and E(M) the set of idempotents of M. We study various forms of subsemigroup generating in affine algebraic monoids and relevant generating problems with kernel data. We determine the structure of minimal irreducible algebraic submonoids containing the kernel, in particular, of M = G ∪ ker(M). We also prove that M with a dense unit group is regular if and only if M = ? E(M), G ? and ? E(M) ? is regular.     

ON NUMBER OF LEAVES ANDBANDWIDTH OF TREES

1.IntroductionFOragraphG=(V,E)oforderp,aonetoonemappingfromVinto{l,2,',p}iscalledanumberingofG.Definition1.1.SupposefisanumberingofG.LetBj(G)=(u57teif(u)--f(v)l.ThebandwidthofG,denotedbyB(G),isdefinedbyB(G)=min{Bf(G)IfisanumberingofG}.Thebandwidthproblemofgraphshasbecomeveryimportantsincethemid-sixties(see[21or[4]).Itisverydifficulttodeterminethebandwidthofagraph.GareyetallllshowedthatthebandwidthproblemisNP-completeevenifitisrestrictedtotreeswithmaximumdegree3.Soitisinterestingtoe…     

Some results on the achromatic number

Let G be a simple graph. The achromatic number ψ(G) is the largest number of colors possible in a proper vertex coloring of G in which each pair of colors is adjacent somewhere in G. For any positive integer m, let q(m) be the largest integer k such that ≤ m. We show that the problem of determining the achromatic number of a tree is NP-hard. We further prove that almost all trees T satisfy ψ (T) = q(m), where m is the number of edges in T. Lastly, for fixed d and ϵ > 0, we show that there is an integer N₀ = N₀(d, ϵ) such that if G is a graph with maximum degree at most d, and m ≥ N₀ edges, then (1 - ϵ)q(m) ≤ ψ (G) ≤ q(m). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 129–136, 1997