Weinberg bounds over nonspherical graphs

Let Aut(G) and E(G) denote the automorphism group and the edge set of a graph G, respectively. Weinberg's Theorem states that 4 is a constant sharp upper bound on the ratio |Aut(G)|/|E(G)| over planar (or spherical) 3‐connected graphs G. We have obtained various analogues of this theorem for nonspherical graphs, introducing two Weinberg‐type bounds for an arbitrary closed surface Σ, namely: where supremum is taken over the polyhedral graphs G with respect to Σ for W_P(Σ) and over the graphs G triangulating Σ for W_T(Σ). We have proved that Weinberg bounds are finite for any surface; in particular: W_P = W_T = 48 for the projective plane, and W_T = 240 for the torus. We have also proved that the original Weinberg bound of 4 holds over the graphs G triangulating the projective plane with at least 8 vertices and, in general, for the graphs of sufficiently large order triangulating a fixed closed surface Σ. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 220–236, 2000     

Boxicity of Graphs on Surfaces

The boxicity of a graph G = (V, E) is the least integer k for which there exist k interval graphs G _i  = (V, E _i ), 1 ≤ i ≤ k, such that ${E = E_1 \cap \cdots \cap E_k}$ . Scheinerman proved in 1984 that outerplanar graphs have boxicity at most two and Thomassen proved in 1986 that planar graphs have boxicity at most three. In this note we prove that the boxicity of toroidal graphs is at most 7, and that the boxicity of graphs embeddable in a surface Σ of genus g is at most 5g + 3. This result yields improved bounds on the dimension of the adjacency poset of graphs on surfaces.     

G-covering systems of subgroups for the class of supersoluble groups

Let ? be a class of groups. Given a group G, assign to G some set of its subgroups Σ = Σ(G). We say that Σ is a G-covering system of subgroups for ? (or, in other words, an ?-covering system of subgroups in G) if G ∈ ? wherever either Σ = ? or Σ ≠ ? and every subgroup in Σ belongs to ?. In this paper, we provide some nontrivial sets of subgroups of a finite group G which are G-covering subgroup systems for the class of supersoluble groups. These are the generalizations of some recent results, such as in [1–3].     

Neighborhood perfect graphs

The notion of neighborhood perfect graphs is introduced here as follows. Let G be a graph, α_N(G) denote the maximum number of edges such that no two of them belong to the same subgraph of G induced by the (closed) neighborhood of some vertex; let ϱ_N(G) be the minimum number of vertices whose neighborhood subgraph cover the edge set of G. Then G is called neighborhood perfect if ϱ_N(G′) = α_N(G′) holds for every induced subgraph G′ of G. It is expected that neighborhood perfect graphs are perfect also in the sense of Berge. We characterized here those chordal graphs which are neighborhood perfect. In addition, an algorithm to computer ϱ_N(G) = α_N(G) is given for interval graphs.     

On the non-orientable genus of a 2-connected graph

In earlier works, additivity theorems for the genus and Euler genus of unions of graphs at two points have been given. In this work, the analogous result for the non-orientable genus is given. If Σ is obtained from the sphere by the addition of k>0 crosscaps, define γ(Σ) to be k. For a graph G, define γ(G) to be the least element in the set {γ(Σ) | G embeds in Σ}.Theorem. Let H₁ and H₂ be connected graphs such that H₁ ∩ H₂ consists of the isolated vertices v and w. Then, for some μ ϵ −1, 0, 1, 2, γ(H₁ ∪ H₂) = γ(H₁) + γ(H₂) + μ.A formula for μ is given.     

Two applications of semi-stable graphs

A Michigan graph G on a vertex set V is called semi-stable if for some υ?V, Γ(G_υ) = Γ(G)_υ. It can be shown that all regular graphs are semi-stable and this fact is used to show (i) that if Γ(G) is doubly transitive then G = K_n or K?_n, and (ii) that Γ(G) can be recovered from Γ(G_υ). The second result is extended to the case of stable graphs.     

On the Evaluation of the Tutte Polynomial at the Points (1, –1) and (2, –1)

Motivated by the identity t (K _n+2; 1, –1) = t (K _n ; 2, –1), where t(G; x, y) is the Tutte polynomial of a graph G, we search for graphs G having the property that there is a pair of vertices u, v such that t(G; 1, –1) = t(G – {u, v}; 2, –1). Our main result gives a sufficient condition for a graph to have this property; moreover, it describes the graphs for which the property still holds when each vertex is replaced by a clique or a coclique of arbitrary order. In particular, we show that the property holds for the class of threshold graphs, a well-studied class of perfect graphs.     

Vertex-transitive graphs: Symmetric graphs of prime valency

Let G be a group acting symmetrically on a graph Σ, let G₁ be a subgroup of G minimal among those that act symmetrically on Σ, and let G₂ be a subgroup of G₁ maximal among those normal subgroups of G₁ which contain no member except 1 which fixes a vertex of Σ. The most precise result of this paper is that if Σ has prime valency p, then either Σ is a bipartite graph or G₂ acts regularly on Σ or G₁ | G₂ is a simple group which acts symmetrically on a graph of valency p which can be constructed from Σ and does not have more vertices than Σ. The results on vertex-transitive groups necessary to establish results like this are also included.     

Distance spectra and distance energy of integral circulant graphs

The distance energy of a graph G is a recently developed energy-type invariant, defined as the sum of absolute values of the eigenvalues of the distance matrix of G. There was a vast research for the pairs and families of non-cospectral graphs having equal distance energy, and most of these constructions were based on the join of graphs. A graph is called circulant if it is Cayley graph on the circulant group, i.e. its adjacency matrix is circulant. A graph is called integral if all eigenvalues of its adjacency matrix are integers. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer. In this paper, we characterize the distance spectra of integral circulant graphs and prove that these graphs have integral eigenvalues of distance matrix D. Furthermore, we calculate the distance spectra and distance energy of unitary Cayley graphs. In conclusion, we present two families of pairs (G₁,G₂) of integral circulant graphs with equal distance energy - in the first family G₁ is subgraph of G₂, while in the second family the diameter of both graphs is three.     

Uniquely Total Colorable Graphs

Uniquely vertex colorable graphs and uniquely edge colorable graphs have been studied extensively by different authors. The literature on the similar problem for total coloring is void. In this paper we study this concept and, among other results, we prove that if a graph G ≠ K ₂ is uniquely total colorable, then χ″(G) = Δ + 1. Our results support the following conjecture: empty graphs, paths, and cycles of order 3k, k a natural number, are the only uniquely total colorable graphs.     

Eccentric graphs

For any graph G we define the eccentric graph G_e on the same set of vertices, by joining two vertices in G_e if and only if one of the vertices has maximum possible distance from the other. The following results are given in this paper:

• (1)A few general properties of eccentric graphs.
• (2)A characterization of graphs G with G_e = K_p and with G_e = pK₂.
• (3)A solution of the equation G_e = G¯.

     

On the edge reconstruction of graphs embedded on surfaces

In this paper, we proved that ifG is a 3-connected graph of minimum valency δ = 6χ + 5 with α a non-negative integer and if there exists an embedding ψ ofG on a surface Σ of characteristic ?(Σ) = — α|V(G)∣+ β with the representativity of the embedding ψ ≥ 3, where ψ ε 0,1, thenG is edge reconstructible.     

Uniformly finite-to-one and onto extensions of homomorphisms between strongly connected graphs

For a homomorphism between directed graphs G₁ and G₂, its extension is the mapping of the set of all paths in G₁ into the set of all paths in G₂ obtained by naturally extending it. We investigate the properties of uniformly finite-to-one and onto extensions of homomorphisms of directed graphs, essentially the properties of uniformly finite-to-one and onto extensions of homomorphisms between strongly connected directed graphs. We also describe applications of our results on homomorphisms of directed graphs to the theory of a class of symbolic flows called subshifts of finite type.     

Join of two graphs admits a nowhere-zero 3-flow

Let G be a graph, and λ the smallest integer for which G has a nowherezero λ-flow, i.e., an integer λ for which G admits a nowhere-zero λ-flow, but it does not admit a (λ ? 1)-flow. We denote the minimum flow number of G by Λ(G). In this paper we show that if G and H are two arbitrary graphs and G has no isolated vertex, then Λ(G ∨ H) ? 3 except two cases: (i) One of the graphs G and H is K ₂ and the other is 1-regular. (ii) H = K ₁ and G is a graph with at least one isolated vertex or a component whose every block is an odd cycle. Among other results, we prove that for every two graphs G and H with at least 4 vertices, Λ(G ∨ H) ? 3.     

Total chromatic number of graphs with small genus

Given a graph G, a total k-coloring of G is a simultaneous coloring of the vertices and edges of G with k colors. Denote χ_ve (G) the total chromatic number of G, and c(Σ) the Euler characteristic of a surfase Σ. In this paper, we prove that for any simple graph G which can be embedded in a surface Σ with Euler characteristic c(Σ), χ_ve (G) = Δ (G) + 1 if c(Σ) > 0 and Δ (G) ≥ 13, or, if c(Σ) = 0 and Δ (G) ≥ 14. This result generalizes results in [3], [4], [5] by Borodin.     

A note on Ramsey multiplicity

If G₁ and G₂ are graphs and the Ramsey number r(G₁, G₂) = p, then the fewest number of G₁ in G and G₂ in ? (G complement) that occur in a graph G on p points is called the Ramsey multiplicity and denoted R(G₁, G₂). In [2, 3] the diagonal (i.e. G₁ = G₂) Ramsey multiplicities are derived for graphs on 3 and 4 points, with the exception of K₄. In this note an upper bound is established for R(K_s, K₁). Specifically, we show that R(K₄, K₄) ? 12.     

Codichromatic graphs

A construction is given for two non-isomorphic graphs G and H such that _χ(G; x, y) = _χ(H; x, y). The two graphs can be made strict, and even 5-connected.     

On the edge-connectivity and restricted edge-connectivity of a product of graphs

The product graph G_m*G_p of two given graphs G_m and G_p was defined by Bermond et al. [Large graphs with given degree and diameter II, J. Combin. Theory Ser. B 36 (1984) 32-48]. For this kind of graphs we provide bounds for two connectivity parameters (λ and λ^′, edge-connectivity and restricted edge-connectivity, respectively), and state sufficient conditions to guarantee optimal values of these parameters. Moreover, we compare our results with other previous related ones for permutation graphs and cartesian product graphs, obtaining several extensions and improvements. In this regard, for any two connected graphs G_m, G_p of minimum degrees δ(G_m), δ(G_p), respectively, we show that λ(G_m*G_p) is lower bounded by both δ(G_m)+λ(G_p) and δ(G_p)+λ(G_m), an improvement of what is known for the edge-connectivity of G_m×G_p.     

On the seidel integral complete multipartite graphs

For a simple undirected graph G, denote by A(G) the (0,1)-adjacency matrix of G. Let thematrix S(G) = J-I-2A(G) be its Seidel matrix, and let S _G (??) = det(??I-S(G)) be its Seidel characteristic polynomial, where I is an identity matrix and J is a square matrix all of whose entries are equal to 1. If all eigenvalues of S _G (??) are integral, then the graph G is called S-integral. In this paper, our main goal is to investigate the eigenvalues of S _G (??) for the complete multipartite graphs G = $G = K_{n_1 ,n_2 ,...n_t } $ . A necessary and sufficient condition for the complete tripartite graphs K _m,n,t and the complete multipartite graphs to be S-integral is given, respectively.