On groups with large character degree sums

Let G be a finite group, and let T(G) be the sum of all complex irreducible character degrees of G. Define ${f(G) = \frac{T(G)}{|G|}}$ . In this paper, we show that if G is a finite group and ${f(G) > \frac{4}{15}}$ , then G is solvable.     

Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999     

Long cycles in graphs with large degree sums and neighborhood unions

We present and prove several results concerning the length of longest cycles in 2-connected or 1-tough graphs with large degree sums. These results improve many known results on long cycles in these graphs. We also consider the sharpness of the results and discuss some possible strengthenings. © 1996 John Wiley & Sons, Inc.     

Complete subgraphs are elusive

We would like to decide whether a graph with a given vertex set has a certain property. We do this by probing the pairs of vertices one by one, i.e., asking whether a given pair of vertices is an edge or not. At each stage we make full use of the information we have up to that point. If there is an algorithm (a sequence of probes depending on the previous information) that allows us to come to a decision before checking every pair, the property is said to be incomplete, otherwise it is called complete or elusive. We show that the property of containing a complete subgraph with a given number of vertices is elusive. The proof also implies that the property of being r-chromatic (r fixed) is elusive.     

Large induced subgraphs with equated maximum degree

For a graph G, denote by f_k(G) the smallest number of vertices that must be deleted from G so that the remaining induced subgraph has its maximum degree shared by at least k vertices. It is not difficult to prove that there are graphs for which already , where n is the number of vertices of G. It is conjectured that for every fixed k. We prove this for k=2,3. While the proof for the case k=2 is easy, already the proof for the case k=3 is considerably more difficult. The case k=4 remains open.A related parameter, s_k(G), denotes the maximum integer m so that there are k vertex-disjoint subgraphs of G, each with m vertices, and with the same maximum degree. We prove that for every fixed k, s_k(G)≥n/k−o(n). The proof relies on probabilistic arguments.     

Heavy cycles in k-connected weighted graphs with large weighted degree sums

A weighted graph is one in which every edge e is assigned a nonnegative number w(e), called the weight of e. The weight of a cycle is defined as the sum of the weights of its edges. The weighted degree of a vertex is the sum of the weights of the edges incident with it. In this paper, we prove that: Let G be a k-connected weighted graph with k?2. Then G contains either a Hamilton cycle or a cycle of weight at least 2m/(k+1), if G satisfies the following conditions: (1) The weighted degree sum of any k+1 pairwise nonadjacent vertices is at least m; (2) In each induced claw and each induced modified claw of G, all edges have the same weight. This generalizes an early result of Enomoto et al. on the existence of heavy cycles in k-connected weighted graphs.     

Relative length of long paths and cycles in graphs with large degree sums

For a graph G, p(G) denotes the order of a longest path in G and c(G) the order of a longest cycle. We show that if G is a connected graph n ≥ 3 vertices such that d(u) + d(v) + d(w) ≧ n for all triples u, v, w of independent vertices, then G satisfies c(G) ≥ p(G) – 1, or G is in one of six families of exceptional graphs. This generalizes results of Bondy and of Bauer, Morgana, Schmeichel, and Veldman. © 1995, John Wiley & Sons, Inc.     

Graphs with unavoidable subgraphs with large degrees

Let ??(n, m) denote the class of simple graphs on n vertices and m edges and let G ∈ ?? (n, m). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of given lengths, complete graphs, etc. For example, Turan's theorem gives a sufficient condition for G to contain a K_{k + 1} in terms of the number of edges in G. In this paper we prove that, for m = αn², α > (k - 1)/2k, G contains a K_{k + 1}, each vertex of which has degree at least f(α)n and determine the best possible f(α). For m = ?n²/4? + 1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for m = αn², α > 0 we establish that G contains a subgraph H with δ(H) ≥ f(α, n) and determine the best possible value of f(α, n).     

Complete rational arithmetic sums

Let {itq} > 1 be an integer number, \(f\left( x \right) = {a_n}{x^n} + \ldots + {a_1}x + {a_0}\) be a polynomial with integer coefficients, and ({ita}{in{itn}}, . . . ,{ita}{in1},{itq}) = 1. The following estimate is valid: \(\left| {S\left( {\frac{{f\left( x \right)}}{q}} \right)} \right| = \left| {\sum\limits_{x = 1}^q \rho \left( {\frac{{f\left( x \right)}}{q}} \right)} \right| \ll {q^{1 - 1/n}}\), where \(\rho \left( t \right) = 0,5 - \left\{ t \right\}\).     

Finding maximum subgraphs with relatively large vertex connectivity

We consider a clique relaxation model based on the concept of relative vertex connectivity. It extends the classical definition of a k-vertex-connected subgraph by requiring that the minimum number of vertices whose removal results in a disconnected (or a trivial) graph is proportional to the size of this subgraph, rather than fixed at k. Consequently, we further generalize the proposed approach to require vertex-connectivity of a subgraph to be some function f of its size. We discuss connections of the proposed models with other clique relaxation ideas from the literature and demonstrate that our generalized framework, referred to as f-vertex-connectivity, encompasses other known vertex-connectivity-based models, such as s-bundle and k-block. We study related computational complexity issues and show that finding maximum subgraphs with relatively large vertex connectivity is NP-hard. An interesting special case that extends the R-robust 2-club model recently introduced in the literature, is also considered. In terms of solution techniques, we first develop general linear mixed integer programming (MIP) formulations. Then we describe an effective exact algorithm that iteratively solves a series of simpler MIPs, along with some enhancements, in order to obtain an optimal solution for the original problem. Finally, we perform computational experiments on several classes of random and real-life networks to demonstrate performance of the developed solution approaches and illustrate some properties of the proposed clique relaxation models.     

Largest bipartite subgraphs in triangle-free graphs with maximum degree three

Let G be a triangle-free, loopless graph with maximum degree three. We display a polynomial algorithm which returns a bipartite subgraph of G containing at least ? of the edges of G. Furthermore, we characterize the dodecahedron and the Petersen graph as the only 3-regular, triangle-free, loopless, connected graphs for which no bipartite subgraph has more than this proportion.     

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.     

Covering cycles andk-term degree sums

We show that if , for every stable set , then the vertex set ofG can be covered withk–1 cycles, edges or vertices. This settles a conjecture by Enomoto, Kaneko and Tuza.     

Graphs with many r-cliques have large complete r-partite subgraphs

Let r2 and c>0. Every graph on n vertices with at least cn^rcliques on r vertices contains a complete r-partite subgraphwith r–1 parts of size c^rlog n and one part of size greaterthan n^1–cr–1. This result implies a quantitativeform of the Erdös–Stone theorem.     

Complete subgraphs of the graphs of convex polytopes

It is shown that if three vertices of the graph G(l') of a convex 3-polytope P are chosen, then G(P) contains a refinement of the complete graph C₄ on four vertices, for which the three chosen vertices are principal (that is, correspond to vertices of C₄ in the refinement). In general, all four vertices may not be preassigned as principal. For dimensions d?4, simple (simplicial) d-polytopes are constructed whose graphs contain sets of three (four) vertices, which cannot all be principal in any refinement of C₄₊₁.     

Complete matchings in random subgraphs of the cube

In this article it is shown that for almost every random cube process the hitting time of a complete matching equals the hitting time of having minimal degree (at least) one and also the hitting time of connectedness. It follows from this that if t = (n + c + o(1))2^n?2 for some constant c, then the probability that a random subgraph of the n-cube having precisely t edges has a complete matching tends to e.     

On graphs with small subgraphs of large chromatic number

Bollobás, Erdös, Simonovits, and Szemerédi conjectured [1] that for each positive constantc there exists a constantg(c) such that ifG is any graph which cannot be made 3-chromatic by the omission ofcn ² edges, thenG contains a 4-chromatic subgraph with at mostg(c) vertices. Here we establish the following generalization which was suggested by Erdös [2]: For each positive constantc and positive integerk there exist positive integersf _k(c) andn _o such that ifG is any graph with more thann _o vertices having the property that the chromatic number ofG cannot be made less thank by the omission of at mostcn ² edges, thenG contains ak-chromatic subgraph with at mostf _k(c) vertices.     

Spanning eulerian subgraphs of bounded degree in triangulations

We show that every triangulation of a disk or an annulus has a spanning Eulerian subgraph with maximum degree eight. Since every triangulation in the projective plane, the torus and the Klein bottle has a spanning subgraph which triangulates an annulus, this implies that all triangulations in the projective plane, the torus and the Klein bottle have spanning Eulerian subgraphs with maximum degree at most eight.     

Covering the vertex set of a graph with subgraphs of smaller degree

The problem of covering the vertex set of a graph with subsets spanning subgraphs of smaller degree is studied. The result of this study is applied to give a new bound on the chromatic number of a graph in terms of the maximum vertex-degree of the graph and the maximum number of vertices in a clique of the graph. By using this bound, it is shown that if d is at least 7 and e is at least 4, then there is no regular graph of valency d, chromatic number d, whose smallest circuit has at least e edges; this settles a conjecture of Branko Grünbaum.