Search

Let G be a simple m × n bipartite graph with m ≥ n . We prove that if the minimum degree of G satisfies δ ( G ) ≥ m ∕ 2 + 1 , then G is bipanconnected: for every pair of vertices x , y , and for every appropriate integer 2 ≤ l ≤ 2 n , there is an x , y -path of length l in G .

Let D 2 n denote the dihedral group of order 2 n , where n ≥ 3 . In this article, we build upon the findings of Haggard and McCarthy who, for certain values of n , produced a vertex-minimal graph with dihedral symmetry. Specifically, Haggard considered the situation when n 2 or n is a prime power, and McCarthy investigated the case when n is not divisible by 2 , 3 or 5 . In this article, we assume n is not divisible by 4 and construct a vertex-minimal graph whose automorphism group is isomorphic to D 2 n .

A graph is symmetric if its automorphism group acts transitively on the set of arcs of the graph. In this paper, we classify hexavalent symmetric graphs of order 9 p for each prime p .

A graph is called symmetric if its automorphism group is transitive on its arcs. In this paper, we classify symmetric graphs of order four times an odd square-free integer and valency seven. It is shown that, either the graph is isomorphic to one of 9 specific graphs or its full automorphism group is isomorphic to PSL ( 2 , p ) , PGL ( 2 , p ) , PSL ( 2 , p ) × Z 2 or PGL ( 2 , p ) × Z 2 with p ≡ ± 1 ( mod 7 ) a prime.

A graph is said to be a bi-Cayley graph over a group H if it admits H as a semiregular automorphism group with two vertex-orbits. A bi-dihedrant is a bi-Cayley graph over a dihedral group. In this paper, it is shown that every connected trivalent edge-transitive bi-dihedrant is also vertex-transitive, and then we present a classification of trivalent arc-transitive bi-dihedrants, and study the Cayley property of trivalent vertex-transitive bi-dihedrants.

The strong chromatic index of a graph G, denoted by s(G), is the minimum possible number of colors in a coloring of the edges of G such that each color class is an induced matching. The corresponding fractional parameter is denoted by sf(G).For a bipartite graph G we have sf(G)1.5G2. This follows as an easy consequence of earlier results the fractional variant of Reeds conjecture and the theorem by Faudree, Gyrfs, Schelp and Tuza from 1990. Both these results are tight so it may seem that the bound 1.5G2 is best possible.We break this 1.5 barrier. We prove that sf(G)1.4762G2+G1.5 for every bipartite graph G. The main part of the proof is a structural lemma regarding cliques in L(G)2.

A graph is half-arc-transitive if its automorphism group acts transitively on its vertex set, edge set, but not arc set. Let n be a product of three primes. The problem on the classification of the tetravalent half-arc-transitive graphs of order n has been considered by Xu (1992), Feng et?al. (2007) and Wang and Feng (2010), and it was solved for the cases where n is a prime cube or twice a product of two primes. In this paper, we solve this problem for the remaining cases. In particular, there exist some families of these graphs which have a solvable automorphism group but are not metacirculants.

A graph is symmetric (or arc-transitive) if its automorphism group is transitive on the arc set of the graph. Let r q p be three distinct primes. In this paper, we give a complete classification of connected pentavalent symmetric graphs of order 2 p q r with r ≥ 3 . It is shown that a connected pentavalent symmetric graph Γ of order 2 p q r is isomorphic to one of 20 sporadic coset graphs associated with some simple groups, a coset graph on the group PSL ( 2 , p ) or PGL ( 2 , p ) with p ≥ 29 and Aut ( Γ ) ≅ PSL ( 2 , p ) or PGL ( 2 , p ) respectively, or a 1-regular graph given in Feng and Li (2011). The connected pentavalent symmetric graphs of order 4 p q have been classified before.

Based on an acyclic orientation of the Z -transformation graph, a finite distributive lattice (FDL for short) M ( G ) is established on the set of all 1-factors of a plane (weakly) elementary bipartite graph G . For an FDL L , if there exists a plane bipartite graph G such that L is isomorphic to M ( G ) , then L is called a matchable FDL. A natural question arises: Is every FDL a matchable FDL? In this paper we give a negative answer to this question. Further, we obtain a series of non-matchable FDLs by characterizing sub-structures of matchable FDLs with cut-elements.

We give a determinant expression for the zeta function of the middle graph of a semiregular bipartite graph G and express the complexity of the middle graph of G by using the complexity of G . As a corollary, we obtain an explicit formula for the complexity of the middle graph of a complete bipartite graph.

A graph is symmetric if its automorphism group is transitive on the arc set of the graph. In this paper, we classify connected cubic symmetric graphs of order 8p^3 for each prime p. All those symmetric graphs are explicitly constructed as normal Cayley graphs on some groups of order 8p^3, and their automorphism groups are determined. There is a unique connected cubic symmetric graph of order 64. All connected cubic symmetric graphs of order 8p^3 for p>=3 are regular covers of the three dimensional hypercube Q"3, and consist of four infinite families, of which two families exist if and only if 3|(p-1) and the other two families exist for each odd prime p. In each family, there is a unique graph for a given order.

A G-design of order v is an edge disjoint decomposition of K"v into copies of the graph G. A metamorphosis of a G-design of order v into a (G-e)-design of order v is obtained by retaining the graph G-e from each block of G in the design, and rearranging the remaining edges to form further copies of G-e. Here, we prove that if a graph G with n edges admits an @a-labelling and the graph G-e admits a @r^+-labelling, then there is a metamorphosis of a G-design of order 2n(n-1)x+1 into a (G-e)-design of the same order for all integers x.

In this paper, we consider the relations between the critical group of a regular graph G and that of its clique-inserted graph (or para-line graph) C(G). First, we construct a group homomorphism between these two critical groups of G and C(G). Based on the homomorphism, we show that the critical group of G is isomorphic to a quotient of that of C(G) if G is not bipartite, and the minimal number of generators for the critical group of C(G) is equal to the number of independent cycles in G if G is 2-edge connected. Second, by computing the Smith normal form of the Laplacian matrix of a graph, we obtain invariant factors of critical groups for some small regular graphs and their corresponding clique-inserted graphs.

Let S be a set of transpositions that generates the symmetric group S n , where n ≥ 3 . The transposition graph T ( S ) is defined to be the graph with vertex set { 1 , … , n } and with vertices i and j being adjacent in T ( S ) whenever ( i , j ) ∈ S . We prove that if the girth of the transposition graph T ( S ) is at least 5, then the automorphism group of the Cayley graph Cay ( S n , S ) is the semidirect product R ( S n ) ⋊ Aut ( S n , S ) , where Aut ( S n , S ) is the set of automorphisms of S n that fixes S . This strengthens a result of Feng on transposition graphs that are trees. We also prove that if the transposition graph T ( S ) is a 4 -cycle, then the set of automorphisms of the Cayley graph Cay ( S 4 , S ) that fixes a vertex and each of its neighbors is isomorphic to the Klein 4-group and hence is nontrivial. We thus identify the existence of 4-cycles in the transposition graph as being an important factor in causing a potentially larger automorphism group of the Cayley graph.

The nullity of a graph G , denoted by η ( G ) , is the multiplicity of 0 in the spectrum of G . Nullity of a (molecular) graph (e.g., a bipartite graph corresponding to an alternant hydrocarbon) has important applications in quantum chemistry and Huckel molecular orbital (HMO) theory. A famous problem, posed by Collatz and Sinogowitz in 1957, asks to characterize all graphs with positive nullity. Clearly, det A ( G ) = 0 if and only if η ( G ) > 0 . So, examining the determinant of a graph is a way to attack this problem. For a graph G , we define the matching core of G to be the graph obtained from G by successively deleting each pendant vertex along with its neighbour. In this paper, we show that the determinant of a graph G with all cycle lengths divisible by four (e.g., the 1-subdivision of a bipartite graph), is 0 or ( − 1 ) | V ( G ) | / 2 . Furthermore, the determinant is 0 if and only if the matching core of G is nonempty.

It has long been known that the class of connected nonbipartite graphs (with loops allowed) obeys unique prime factorization over the direct product of graphs. Moreover, it is known that prime factorization is not necessarily unique in the class of connected bipartite graphs. But any prime factorization of a connected bipartite graph has exactly one bipartite factor. Moreover, empirical evidence suggests that any two prime factorings of a given connected bipartite graph have isomorphic bipartite factors. This prompts us to conjecture that among all the different prime factorings of a given connected bipartite graph, the bipartite factor is always the same. The present paper proves that the conjecture is true for graphs that have a K 2 factor. (Even in this simple case, the result is surprisingly nontrivial.) Further, we indicate how to compute all possible prime factorings of such a graph. In addition, we show how the truth of the conjecture (in general) would lead to a method of finding all distinct prime factorings of any connected bipartite graph. To accomplish this, we prove the following preliminary result, which is the main technical result of the paper: Suppose A × B is connected and bipartite, and B is the bipartite factor. If A × B admits an involution that reverses partite sets, then B also admits such an involution.

In this paper, we give some necessary and sufficient conditions for decomposing the complete bipartite graph K m , n into paths P k + 1 and stars S k + 1 with k edges each. In particular, we find necessary and sufficient conditions for accomplishing this when m > k and n ≥ 3 k , and we give a complete solution when k = 3 . We also apply the results to show that for nonnegative integers p and q and positive integers n and k with n ≥ 4 k , there exists a decomposition of the complete graph K n into p copies of P k + 1 and q copies of S k + 1 if and only if k ( p + q ) = n 2 .

Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow. Let F 12 be a family of graphs such that G ∈ F 12 if and only if G is a simple bipartite graph on 12 vertices and δ ( G ) = 4 . Let G be a simple bipartite graph on n vertices. It is proved in this paper that if δ ( G ) ≥ ⌈ n 4 ⌉ + 1 , then G admits a nowhere-zero 3-flow with only one exceptional graph. Moreover, if G ∉ F 12 with the minimum degree at least ⌈ n 4 ⌉ + 1 is Z 3 -connected. The bound is best possible in the sense that the lower bound for the minimum degree cannot be decreased.

A classification is given for connected edge-transitive tetravalent Cayley graphs of square-free order. The classification shows that, with a few exceptions, a connected edge-transitive tetravalent Cayley graph of square-free order is either arc-regular or edge-regular. It thus provides a generic construction of half-transitive graphs of valency 4.

Homomorphisms to a given graph H ( H -colourings) are considered in the literature among other graph colouring concepts. We restrict our attention to a special class of H -colourings, namely H is assumed to be a star. Our additional requirement is that the set of vertices of a graph G mapped into the central vertex of the star and any other colour class induce in G an acyclic subgraph. We investigate the existence of such a homomorphism to a star of given order. The complexity of this problem is studied. Moreover, the smallest order of a star for which a homomorphism of a given graph G with desired features exists is considered. Some exact values and many bounds of this number for chordal bipartite graphs, cylinders, grids, in particular hypercubes, are given. As an application of these results, we obtain some bounds on the cardinality of the minimum feedback vertex set for specified graph classes.

A graph is k-supereulerian if it has a spanning even subgraph with at most k components. We show that if G is a connected graph and G′ is the (collapsible) reduction of G, then G is k-supereulerian if and only if G′ is k-supereulerian. This extends Catlin’s reduction theorem in [P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44]. For a graph G, let F(G) be the minimum number of edges whose addition to G create a spanning supergraph containing two edge-disjoint spanning trees. We prove that if G is a connected graph with F(G)≤k, where k is a positive integer, then either G is k-supereulerian or G can be contracted to a tree of order k+1. This is a best possible result which extends another theorem of Catlin, in [P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44]. Finally, we use these results to give a sufficient condition on the minimum degree for a graph G to bek-supereulerian.

It is proved that the vertices of a cubic bipartite plane graph can be colored with four colors such that each face meets all four colors. This is tight, since any such graph contains at least six faces of size four.

Tutte introduced the theory of nowhere zero flows and showed that a plane graph G has a face k -coloring if and only if G has a nowhere zero A -flow, for any Abelian group A with | A | ? k . In 1992, Jaeger et?al. 9] extended nowhere zero flows to group connectivity of graphs: given an orientation D of a graph G , if for any b : V ( G ) ? A with ? v ? V ( G ) b ( v ) = 0 , there always exists a map f : E ( G ) ? A - { 0 } , such that at each v ? V ( G ) , ? e = v w ?is?directed?from? v ?to? w f ( e ) - ? e = u v ?is?directed?from? u ?to? v f ( e ) = b ( v ) in A , then G is A -connected. Let Z 3 denote the cyclic group of order 3. In 9], Jaeger et?al. (1992) conjectured that every 5-edge-connected graph is Z 3 -connected. In this paper, we proved the following. (i)Every 5-edge-connected graph is Z 3 -connected if and only if every 5-edge-connected line graph is Z 3 -connected.(ii)Every 6-edge-connected triangular line graph is Z 3 -connected.(iii)Every 7-edge-connected triangular claw-free graph is Z 3 -connected. In particular, every 6-edge-connected triangular line graph and every 7-edge-connected triangular claw-free graph have a nowhere zero 3-flow.

A near perfect matching is a matching covering all but one vertex in a graph. Let G be a connected graph and [email protected]?(|V(G)|-2)/2 be a positive integer. If any n independent edges in G are contained in a near perfect matching, then G is said to be defectn-extendable. In this paper, we first characterize defect n-extendable bipartite graph G with n=1 or @k(G)>=2 respectively using M-alternating paths. Furthermore, we present a construction characterization of defect n-extendable bipartite graph G with n>=2 and @k(G)=1. It is also shown that these characterizations can be transformed to polynomial time algorithms to determine if a given bipartite graph is defect n-extendable.

A graph is half-arc-transitive if its automorphism group acts transitively on its vertex set, edge set, but not arc set. In this paper, we show that there is no tetravalent half-arc-transitive graph of order 2p^2.

Given natural numbers n>=3 and [email protected]?a,[email protected]?n-1, the rose window graph R"n(a,r) is a quartic graph with vertex set {x"i|[email protected]?Z"n}@?{y"i|[email protected]?Z"n} and edge set {{x"i,x"i"+"1}|[email protected]?Z"n}@?{{y"i,y"i"+"r}|[email protected]?Z"n}@?{{x"i,y"i}|[email protected]?Z"n}@?{{x"i"+"a,y"i}|[email protected]?Z"n}. In this paper rotary maps on rose window graphs are considered. In particular, we answer the question posed in [S. Wilson, Rose window graphs, Ars Math. Contemp. 1 (2008), 7-19. http://amc.imfm.si/index.php/amc/issue/view/5] concerning which of these graphs underlie a rotary map.

For any [email protected]?N, the k-subdivision of graph G is a simple graph G^1^k which is constructed by replacing each edge of G with a path of length k. In this paper we introduce the mth power of the n-subdivision of G, as a fractional power of G, denoted by G^m^n. In this regard, we investigate the chromatic number and clique number of fractional power of graphs. Also, we conjecture that @g(G^m^n)[email protected](G^m^n) provided that G is a connected graph with @D(G)>=3 and mn

A regular cover of a graph is said to be an edge-transitive cover if the fibre-preserving automorphism subgroup acts edge-transitively on the covering graph. In this paper we classify edge-transitive regular Z"n-covers of the Heawood graph, and obtain a new infinite family of one-regular cubic graphs. Also, as an application of the classification of edge-transitive regular Z"n-covers of the Heawood graph, we prove that any bipartite edge-transitive cubic graph of order 14p is isomorphic to a normal Cayley graph of dihedral group if the prime p>13.

An edge-coloured graph G is a vertex set V(G) together with m edge sets distinguished by m colours. Let π be a permutation on {1,2,…,m}. We define a switching operation consisting of π acting on the edge colours similar to Seidel switching, to switching classes as studied by Babai and Cameron, and to the pushing operation studied by Klostermeyer and MacGillivray. An edge-coloured graph G is π-permutably homomorphic (respectively π-permutably isomorphic) to an edge-coloured graph H if some sequence of switches on G produces an edge-coloured graph homomorphic (respectively isomorphic) to H. We study the π-homomorphism and π-isomorphism operations, relating them to homomorphisms and isomorphisms of a constructed edge-coloured graph that we introduce called a colour switching graph. Finally, we identify those edge-coloured graphs H with the property that G is homomorphic to H if and only if any switch of G is homomorphic to H. It turns out that such an H is precisely a colour switching graph. As a corollary to our work, we settle an open problem of Klostermeyer and MacGillivray.

A graph G is said to be determined by its Q-spectrum if with respect to the signless Laplacian matrix Q, any graph having the same spectrum as G is isomorphic to G. The lollipop graph, denoted by Hn,p, is obtained by appending a cycle Cp to a pendant vertex of a path Pn−p. In this paper, it is proved that all lollipop graphs are determined by their Q-spectra.

A half-arc-transitive graph is a vertex- and edge- but not arc-transitive graph. Following Alspach and Parsons, a metacirculant graph is a graph admitting a transitive group generated by two automorphisms @r and @s, where @r is (m,n)-semiregular for some integers m>=1 and n>=2, and where @s normalizes @r, cyclically permuting the orbits of @r in such a way that @s^m has at least one fixed vertex. In a recent paper Marusic and the author showed that each connected quartic half-arc-transitive metacirculant belongs to one (or possibly more) of four classes of such graphs, reflecting the structure of the quotient graph relative to the semiregular automorphism @r. One of these classes coincides with the class of the so-called tightly-attached graphs, which have already been completely classified. In this paper a complete classification of the second of these classes, that is the class of quartic half-arc-transitive metacirculants for which the quotient graph relative to the semiregular automorphism @r is a cycle with a loop at each vertex, is given.

It is proved that if G is a plane embedding of a K"4-minor-free graph with maximum degree @D, then G is entirely 7-choosable if @[email protected]?4 and G is entirely (@D+2)-choosable if @D>=5; that is, if every vertex, edge and face of G is given a list of max{7,@D+2} colours, then every element can be given a colour from its list such that no two adjacent or incident elements are given the same colour. It is proved also that this result holds if G is a plane embedding of a K"2","3-minor-free graph or a (K"[email protected]?+(K"[email protected]?K"2))-minor-free graph. As a special case this proves that the Entire Coluring Conjecture, that a plane graph is entirely (@D+4)-colourable, holds if G is a plane embedding of a K"4-minor-free graph, a K"2","3-minor-free graph or a (K"[email protected]?+(K"[email protected]?K"2))-minor-free graph.

A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3.

For a 2-factor F of a connected graph G, we consider G−F, which is the graph obtained from G by removing all the edges of F. If G−F is connected, F is said to be a non-separating 2-factor. In this paper we study a sufficient condition for a 2r-regular connected graph G to have such a 2-factor. As a result, we show that a 2r-regular connected graph G has a non-separating 2-factor whenever the number of vertices of G does not exceed 2r2+r.

It is well-known that the minimum number of vertices for a triangle-free 4-chromatic graph is 11, and the Grotzsch graph is just such a graph. In this paper, we show that every non-bipartite triangle-free graph G of order not greater than 10 has @g"l(G)=3. Combined with a known result by Hanson et al. [D. Hanson, G. MacGillivray, B. Toft, Choosability of bipartite graphs, Ars Combin. 44 (1996) 183-192] that every bipartite graph of order not greater than 13 is 3-choosable, we conclude that the minimum number of vertices for a triangle-free graph with @g"l(G)=4 is also 11.

We generalize earlier work which gave a method of construction for bipartite graphs which are obtained as the set of maximal or minimal elements of a certain cycle-free partial order. The method is extended here to produce a 1-arc-transitive bipartite graph in a ‘free’ way, starting with any partial order with greatest and least element and with instructions on its points about how they will ramify in the extension. A key feature of our work is the interplay between properties of the initial partial order, the extended partial order, and the bipartite graph which results. We also extend the earlier work by giving a complete characterization of all 2-CS-transitive cycle-free partial orders. In addition, we discuss the completeness of the constructed partial orders, in the sense of Dedekind and MacNeille, and remark that the bipartite graph constructed can only be 2-arc-transitive in the cycle-free case.

An r-edge-coloring of a graph G is a surjective assignment of r colors to the edges of G. A heterochromatic tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by t"r(G), is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we give an explicit formula for the heterochromatic tree partition number of an r-edge-colored complete bipartite graph K"m","n.

We prove results concerning the distribution of 4-contractible edges in a 4-connected graph G in connection with the edges of G not contained in a triangle. As a corollary, we show that if G is 4-regular 4-connected graph, then the number of 4-contractible edges of G is at least one half of the number of edges of G not contained in a triangle.

Let G=(V,E) be a finite non-empty graph, where V and E are the sets of vertices and edges of G, respectively, and |V|=n and |E|=e. A vertex-magic total labeling (VMTL) is a bijection @l from [email protected]?E to the consecutive integers 1,2,...,n+e with the property that for every [email protected]?V, @l(v)[email protected]?"w"@?"N"("v")@l(v,w)=h, for some constant h. Such a labeling is super if @l(V)={1,2,...,n}. In this paper, two new methods to obtain super VMTLs of graphs are put forward. The first, from a graph G with some characteristics, provides a super VMTL to the graph kG graph composed by the disjoint unions of k copies of G, for a large number of values of k. The second, from a graph G"0 which admits a super VMTL; for instance, the graph kG, provides many super VMTLs for the graphs obtained from G"0 by means of the addition to it of various sets of edges.