Characterisation of Graphs which Underlie Regular Maps on Closed Surfaces

It is proved that a graph K has an embedding as a regular mapon some closed surface if and only if its automorphism groupcontains a subgroup G which acts transitively on the orientededges of K such that the stabiliser G_e of every edge e is dihedralof order 4 and the stabiliser G of each vertex is a dihedralgroup the cyclic subgroup of index 2 of which acts regularlyon the edges incident with . Such a regular embedding can berealised on an orientable surface if and only if the group Ghas a subgroup H of index 2 such that H is the cyclic subgroupof index 2 in G. An analogous result is proved for orientably-regularembeddings.     

Zeta functions of line, middle, total graphs of a graph and their coverings

We consider the (Ihara) zeta functions of line graphs, middle graphs and total graphs of a regular graph and their (regular or irregular) covering graphs. Let L(G), M(G) and T(G) denote the line, middle and total graph of G, respectively. We show that the line, middle and total graph of a (regular and irregular, respectively) covering of a graph G is a (regular and irregular, respectively) covering of L(G), M(G) and T(G), respectively. For a regular graph G, we express the zeta functions of the line, middle and total graph of any (regular or irregular) covering of G in terms of the characteristic polynomial of the covering. Also, the complexities of the line, middle and total graph of any (regular or irregular) covering of G are computed. Furthermore, we discuss the L-functions of the line, middle and total graph of a regular graph G.     

A characterization of Delsarte’s linear programming bound as a ratio bound

It is well known that the ratio bound is an upper bound on the stability number α(G) of a regular graph G. In this note it is proved that, if G is a graph whose edge is a union of classes of a symmetric association scheme, the Delsarte’s linear programming bound can alternatively be stated as the minimum of a set of ratio bounds. This result follows from a recently established relationship between a set of convex quadratic bounds on α(G) and the number ?′(G), a well known variant of the Lovász theta number, which was introduced independently by Schrijver [A. Schrijver, A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory 25 (1979) 425-429] and McEliece et al. [R.J. McEliece, E.R. Rodemich, H.C. Rumsey Jr, The Lovász bound and some generalizations, J. Combin. Inform. System Sci. 3 (1978) 134-152].     

The Harmonious Chromatic Number of Bounded Degree Graphs

A harmonious colouring of a simple graph G is a proper vertexcolouring such that each pair of colours appears together onat most one edge. The harmonious chromatic number h(G) is theleast number of colours in such a colouring. Let d be a fixed positive integer, and >0. We show that thereis a natural number M such that if G is any graph with mM edgesand maximum degree at most d, then the harmonious chromaticnumber h(G) satisfies      

An Upper Bound for List T-Colourings

Erds, Rubin and Taylor showed in 1979 that for any connectedgraph G which is not a complete graph or an odd cycle, ch(G) , where is the maximum degree of a vertex in G and ch(G) isthe choice number of the graph (also proved by Vizing in 1976).They also gave a characterisation of D-choosability. A graphG is D-choosable if, when we assign to each vertex v of G alist containing d(v) elements, where d(v) is the degree of vertexv, we can always choose a proper vertex colouring from theselists, however the lists were chosen. In this paper we shallgeneralise their results on the choice number of G and D-choosabilityto the case where we have T-colourings.     

More on Graph Perturbations

Various modifications of a connected graph G are regarded asperturbations of an adjacency matrix A of G. Several resultsconcerning the resulting changes to the largest eigenvalue ofA are obtained by solving intermediate eigenvalue problems ofthe second type.     

The signless Laplacian spectra of the corona and edge corona of two graphs

We give complete information about the signless Laplacian spectrum of the corona of a graph G ₁ and a regular graph G ₂, and complete information about the signless Laplacian spectrum of the edge corona of a connected regular graph G ₁ and a regular graph G ₂.     

Bass-Tits minimization of automata, quotients of trees and diameters

Let X be a tree and let G=Aut(X), Bass and Tits have given an algorithm to construct the ‘ultimate quotient’ of X by G starting with any quotient of X, an ‘edge-indexed’ graph. Using a sequence of integers that we compute at consecutive steps of the Bass-Tits (BT) algorithm, we give a lower bound on the diameter of the ultimate quotient of a tree by its automorphism group. For a tree X with finite quotient, this gives a lower bound on the minimum number of generators of a uniform X-lattice whose quotient graph coincides with G?X. This also gives a criterion to determine if the ultimate quotient of a tree is infinite. We construct an edge-indexed graph (A,i) for a deterministic finite state automaton and show that the BT algorithm for computing the ultimate quotient of (A,i) coincides with state minimizing algorithm for finite state automata. We obtain a lower bound on the minimum number of states of the minimized automaton. This gives a new proof that language for the word problem in a finitely generated group is regular if and only if the group is finite, and a new proof that the language of the membership problem for a subgroup is regular if and only if the subgroup has finite index.     

Upper minus total domination number of regular graphs

Let Γ _t ^? (G) be upper minus total domination number of G. In this paper, We establish an upper bound of the upper minus total domination number of a regular graph G and characterize the extremal graphs attaining the bound. Thus, we answer an open problem by Yan, Yang and Shan     

Co-cliques and star complements in extremal strongly regular graphs

Suppose that the positive integer μ is the eigenvalue of largest multiplicity in an extremal strongly regular graph G. By interlacing, the independence number of G is at most 4μ² + 4μ − 2. Star complements are used to show that if this bound is attained then either (a) μ = 1 and G is the Schläfli graph or (b) μ = 2 and G is the McLaughlin graph.     

Strengthening Hadwiger's Conjecture

We consider the following strengthening of Hadwiger's Conjecture. Let G be any graph of chromatic number k, S any subset of V(G)which takes all k colours in each proper k-colouring of G. Thenthere are k pairwise adjacent connected subgraphs of G, eachof whose vertex sets has non-trivial intersection with S. We show that the truth of this conjecture for all graphs ofchromatic number k implies the truth of Hadwiger's Conjecturefor all graphs of chromatic number k + 1. We also show thatits truth implies the following statement (which is at firstsight even stronger). For any graph G of chromatic number k and any subset S of V(G),define (S; G) to be the least number of colours that can appearon S in any proper k-colouring of G, and h(S; G) to be the largestnumber of pairwise adjacent connected subgraphs of G each havingnon-trivial intersection with S. Then (S; G) h(S; G). We define the number w(S; G) to be the largest cardinality ofa subset T of S such that, however T is partitioned into pairs(possibly with one spare element), there are vertex-disjointpaths linking the elements in each pair, none passing throughthe spare element if it exists. We show that (S; G) (|S| +w(S; G))/2 for any graph G and subset S of V(G). Finally, we show that for any graph G, (S; G) h(S; G) whenever(S; G) 3. 1991 Mathematics Subject Classification 05C15.     

Common Multiples of Complete Graphs

A graph H is said to divide a graph G if there exists a setS of subgraphs of G, all isomorphic to H, such that the edgeset of G is partitioned by the edge sets of the subgraphs inS. Thus, a graph G is a common multiple of two graphs if eachof the two graphs divides G. This paper considers common multiples of a complete graph oforder m and a complete graph of order n. The complete graphof order n is denoted K_n. In particular, for all positive integersn, the set of integers q for which there exists a common multipleof K₃ and K_n having precisely q edges is determined. It is shown that there exists a common multiple of K₃ and K_nhaving q edges if and only if q 0 (mod 3), q 0 (mod n2) and (1) q 3 n2 when n 5 (mod 6); (2) q (n + 1) n2 when n is even; (3) q {36, 42, 48} when n = 4. The proof of this result uses a variety of techniques includingthe use of Johnson graphs, Skolem and Langford sequences, andequitable partial Steiner triple systems. 2000 MathematicalSubject Classification: 05C70, 05B30, 05B07.     

Nest Representations of Directed Graph Algebras

This paper is a comprehensive study of the nest representationsfor the free semigroupoid algebra L_G of a countable directedgraph G as well as its norm-closed counterpart, the tensor algebraT⁺(G). We prove that the finite-dimensional nest representations separatethe points in L_G, and a fortiori, in T⁺(G). The irreduciblefinite-dimensional representations separate the points in L_Gif and only if G is transitive in components (which is equivalentto being semisimple). Also the upper triangular nest representationsseparate points if and only if for every vertex x T(G) supportinga cycle, x also supports at least one loop edge. We also study faithful nest representations. We prove that L_G(or T⁺(G) admits a faithful irreducible representation if andonly if G is strongly transitive as a directed graph. More generally,we obtain a condition on G which is equivalent to the existenceof a faithful nest representation. We also give a conditionthat determines the existence of a faithful nest representationfor a maximal type N nest. 2000 Mathematics Subject Classification47L80, 47L55, 47L40.     

The Tits Alternative for Cat(0) Cubical Complexes

A Tits alternative theorem is proved in this paper for groupsacting on CAT(0) cubical complexes. That is, a proof is givento show that if G is assumed to be a group for which there isa bound on the orders of its finite subgroups, and if G actsproperly on a finite-dimensional CAT(0) cubical complex, theneither G contains a free subgroup of rank 2, or G is finitelygenerated and virtually abelian. In particular, the above conclusionholds for any group G with a free action on a finite-dimensionalCAT(0) cubical complex. 2000 Mathematics Subject Classification20F67, 20E08.     

A sufficient condition for a regular graph to be class 1

The core GΔ of a simple graph G is the subgraph induced by the vertices of maximum degree. It is well known that the Petersen graph is not 1-factorizable and has property that the core of the graph obtained from it by removing one vertex has maximum degree 2. In this paper, we prove the following result. Let G be a regular graph of even order with d(G) ≥ 3. Suppose that G contains a vertex ν such that the core of G\ν has maximum degree 2. If G is not the Petersen graph, then G is 1-factorizable. © 1993 John Wiley & Sons, Inc.     

Higher Generation Subgroup Sets and the Virtual Cohomological Dimension of Graph Products of Finite Groups

We introduce panels of stabilizer schemes (K, G_*) associatedwith finite intersection-closed subgroup sets of a given groupG, generalizing in some sense Davis' notion of a panel structureon a triangulated manifold for Coxeter groups. Given (K, G_*),we construct a G-complex X with K as a strong fundamental domainand simplex stabilizers conjugate to subgroups in . It turnsout that higher generation properties of in the sense of Abels-Holzare reflected in connectivity properties of X. Given a finite simplicial graph and a non-trivial group G()for every vertex of , the graph product G() is the quotientof the free product of all vertex groups modulo the normal closureof all commutators [G(), G(w)] for which the vertices , w areadjacent. Our main result allows the computation of the virtualcohomological dimension of a graph product with finite vertexgroups in terms of connectivity properties of the underlyinggraph .     

Clique-inserted-graphs and spectral dynamics of clique-inserting

Motivated by studying the spectra of truncated polyhedra, we consider the clique-inserted-graphs. For a regular graph G of degree r>0, the graph obtained by replacing every vertex of G with a complete graph of order r is called the clique-inserted-graph of G, denoted as C(G). We obtain a formula for the characteristic polynomial of C(G) in terms of the characteristic polynomial of G. Furthermore, we analyze the spectral dynamics of iterations of clique-inserting on a regular graph G. For any r-regular graph G with r>2, let S(G) denote the union of the eigenvalue sets of all iterated clique-inserted-graphs of G. We discover that the set of limit points of S(G) is a fractal with the maximum r and the minimum −2, and that the fractal is independent of the structure of the concerned regular graph G as long as the degree r of G is fixed. It follows that for any integer r>2 there exist infinitely many connected r-regular graphs (or, non-regular graphs with r as the maximum degree) with arbitrarily many distinct eigenvalues in an arbitrarily small interval around any given point in the fractal. We also present a formula on the number of spanning trees of any kth iterated clique-inserted-graph and other related results.     

F-Continuous Graphs

For a nontrivial connected graph F, the F-degree of a vertex in a graph G is the number of copies of F in G containing . A graph G is F-continuous (or F-degree continuous) if the F-degrees of every two adjacent vertices of G differ by at most 1. All P₃-continuous graphs are determined. It is observed that if G is a nontrivial connected graph that is F-continuous for all nontrivial connected graphs F, then either G is regular or G is a path. In the case of a 2-connected graph F, however, there always exists a regular graph that is not F-continuous. It is also shown that for every graph H and every 2-connected graph F, there exists an F-continuous graph G containing H as an induced subgraph.     

Acyclic edge coloring of 2‐degenerate graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). A graph is called 2‐degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2‐degenerate graphs properly contains series–parallel graphs, outerplanar graphs, non ? regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G)?Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. We prove the conjecture for 2‐degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2‐degenerate graph with maximum degree Δ, then a′(G)?Δ + 1. © 2010 Wiley Periodicals, Inc. J Graph Theory 69: 1–27, 2012     

Acyclic edge colorings of graphs

A proper coloring of the edges of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. For certain graphs G, a′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ 16 Δ(G) for any graph G. We prove that there exists a constant c such that a′(G) ≤ Δ(G) + 2 for any graph G whose girth is at least cΔ(G) log Δ(G), and conjecture that this upper bound for a′(G) holds for all graphs G. We also show that a′(G) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001