A new characterization of symmetric group by NSE

Let G be a group and ω(G) be the set of element orders of G. Let k ∈ ω(G) and m _k (G) be the number of elements of order k in G. Let nse(G) = {m _k (G): k ∈ ω(G)}. Assume r is a prime number and let G be a group such that nse(G) = nse(S _r ), where S _r is the symmetric group of degree r. In this paper we prove that G ? S _r , if r divides the order of G and r ² does not divide it. To get the conclusion we make use of some well-known results on the prime graphs of finite simple groups and their components.     

<Emphasis Type="Italic">r</Emphasis>-Dynamic Chromatic Number of Some Line Graphs

An r-dynamic coloring of a graph G is a proper coloring c of the vertices such that |c(N(v))| ≥ min {r, deg(v)}, for each v ∈ V (G). The r-dynamic chromatic number of a graph G is the smallest k such that G admits an r-dynamic coloring with k colors. In this paper, we obtain the r-dynamic chromatic number of the line graph of helm graphs H_n for all r between minimum and maximum degree of H_n. Moreover, our proofs are constructive, what means that we give also polynomial time algorithms for the appropriate coloring. Finally, as the first, we define an equivalent model for edge coloring.     

Token Graphs

For a graph G and integer k ≥ 1, we define the token graph F _k (G) to be the graph with vertex set all k-subsets of V(G), where two vertices are adjacent in F _k (G) whenever their symmetric difference is a pair of adjacent vertices in G. Thus vertices of F _k (G) correspond to configurations of k indistinguishable tokens placed at distinct vertices of G, where two configurations are adjacent whenever one configuration can be reached from the other by moving one token along an edge from its current position to an unoccupied vertex. This paper introduces token graphs and studies some of their properties including: connectivity, diameter, cliques, chromatic number, Hamiltonian paths, and Cartesian products of token graphs.     

An Optimal Algorithm for the <Emphasis Type="Italic">k</Emphasis>-Fixed-Endpoint Path Cover on Proper Interval Graphs

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint simple paths that covers the vertices of G, such that the vertices of T are all endpoints of these paths. The goal is to compute a k-fixed-endpoint path cover of G with minimum cardinality. We propose an optimal algorithm for this problem with runtime O(n), where n is the number of intervals in G. This algorithm is based on the Stair Normal Interval Representation (SNIR) matrix that characterizes proper interval graphs. In this characterization, every maximal clique of the graph is represented by one matrix element; the proposed algorithm uses this structural property, in order to determine directly the paths in an optimal solution.     

On the coincidence of Grünberg-Kegel graphs of a finite simple group and its proper subgroup

Let G be a finite group. The spectrum of G is the set ω(G) of orders of all its elements. The subset of prime elements of ω(G) is denoted by π(G). The spectrum ω(G) of a group G defines its prime graph (or Grünberg-Kegel graph) Γ(G) with vertex set π(G), in which any two different vertices r and s are adjacent if and only if the number rs belongs to the set ω(G). We describe all the cases when the prime graphs of a finite simple group and of its proper subgroup coincide.     

Packing spanning graphs from separable families

Let \(\mathcal{G}\) be a separable family of graphs. Then for all positive constants ? and Δ and for every sufficiently large integer n, every sequence G ₁,..., G _t ∈ \(\mathcal{G}\) of graphs of order n and maximum degree at most Δ such that

$$\left( {{G_1}} \right) + \cdots + e\left( {{G_t}} \right) \leqslant \left( {1 - \epsilon } \right)\left( {\begin{array}{*{20}{c}}n \\ 2 \end{array}} \right)$$

packs into K _n . This improves results of Böttcher, Hladký, Piguet and Taraz when \(\mathcal{G}\) is the class of trees and of Messuti, Rödl, and Schacht in the case of a general separable family. The result also implies approximate versions of the Oberwolfach problem and of the Tree Packing Conjecture of Gyárfás and Lehel (1976) for the case that all trees have maximum degree at most Δ.

The proof uses the local resilience of random graphs and a special multi-stage packing procedure.     

Dense 3-uniform hypergraphs containing a large clique

An r-uniform graph C is dense if and only if every proper subgraph G' of G satisfies λ(G') λ(G).,where λ(G) is the Lagrangian of a hypergraph G. In 1980's, Sidorenko showed that π(F), the Turán density of an γ-uniform hypergraph F is r! multiplying the supremum of the Lagrangians of all dense F-hom-free γ-uniform hypergraphs. This connection has been applied in the estimating Turán density of hypergraphs. When γ=2 the result of Motzkin and Straus shows that a graph is dense if and only if it is a complete graph. However,when r ≥ 3, it becomes much harder to estimate the Lagrangians of γ-uniform hypergraphs and to characterize the structure of all dense γ-uniform graphs. The main goal of this note is to give some sufficient conditions for3-uniform graphs with given substructures to be dense. For example, if G is a 3-graph with vertex set [t] and m edges containing [t-1]~(3),then G is dense if and only if m≥{t-2 3)+(t-2 2)+1. We also give a sufficient condition on the number of edges for a 3-uniform hypergraph containing a large clique minus 1 or 2 edges to be dense.     

A variation of a conjecture due to Erdös and Sós

Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e（G） 〉 1/2（k - 1）n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 ＋ 37/2＋ 14 and every graph G on n vertices with e（G） 〉 1/2 （k- 1）n, we prove that there exists a graph G＇ on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.     

A note on the strong edge-coloring of outerplanar graphs with maximum degree 3

A strong k-edge-coloring of a graph G is an assignment of k colors to the edges of G in such a way that any two edges meeting at a common vertex, or being adjacent to the same edge of G, are assigned different colors. The strong chromatic index of G is the smallest integer k for which G has a strong k-edge-coloring. In this paper, we have shown that the strong chromatic index is no larger than 6 for outerplanar graphs with maximum degree 3.     

Hypergraphs with Zero Chromatic Threshold

Let F be an r-uniform hypergraph. The chromatic threshold of the family of F-free, r-uniform hypergraphs is the infimum of all non-negative reals c such that the subfamily of F-free, r-uniform hypergraphs H with minimum degree at least \(c \left( {\begin{array}{c}|V(H)|\\ r-1\end{array}}\right) \) has bounded chromatic number. The study of chromatic thresholds of various graphs has a long history, beginning with the early work of Erd?s and Simonovits. One interesting problem, first proposed by ?uczak and Thomassé and then solved by Allen, Böttcher, Griffiths, Kohayakawa and Morris, is the characterization of graphs having zero chromatic threshold, in particular the fact that there are graphs with non-zero Turán density that have zero chromatic threshold. Here, we make progress on this problem for r-uniform hypergraphs, showing that a large class of hypergraphs have zero chromatic threshold in addition to exhibiting a family of constructions showing another large class of hypergraphs have non-zero chromatic threshold. Our construction is based on a particular product of the Bollobás–Erd?s graphs defined earlier by the authors.     

Some variations on Tverberg’s theorem

Define T(d, r) = (d + 1)(r - 1) + 1. A well known theorem of Tverberg states that if n ≥ T(d, r), then one can partition any set of n points in R^d into r pairwise disjoint subsets whose convex hulls have a common point. The numbers T(d, r) are known as Tverberg numbers. Reay added another parameter k (2 ≤ k ≤ r) and asked: what is the smallest number n, such that every set of n points in R^d admits an r-partition, in such a way that each k of the convex hulls of the r parts meet. Call this number T(d, r, k). Reay conjectured that T(d, r, k) = T(d, r) for all d, r and k. In this paper we prove Reay’s conjecture in the following cases: when k ≥ [d+3/2], and also when d < rk/r-k - 1. The conjecture also holds for the specific values d = 3, r = 4, k = 2 and d = 5, r = 3, k = 2.     

Note on a conjecture for the sum of signless Laplacian eigenvalues

For a simple graph G on n vertices and an integer k with 1 ? k ? n, denote by \(\mathcal{S}^+_k\) (G) the sum of k largest signless Laplacian eigenvalues of G. It was conjectured that \(\mathcal{S}^+_k(G)\leqslant{e}(G)+(^{k+1}_{\;\;2})\) (G) ? e(G) + (k+1 2), where e(G) is the number of edges of G. This conjecture has been proved to be true for all graphs when k ∈ {1, 2, n ? 1, n}, and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all k). In this note, this conjecture is proved to be true for all graphs when k = n ? 2, and for some new classes of graphs.     

Generalized 3-edge-connectivity of Cartesian product graphs

The generalized k-connectivity κ _k (G) of a graph G was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k-edge-connectivity which is defined as λ _k (G) = min{λ(S): S ? V (G) and |S| = k}, where λ(S) denotes the maximum number l of pairwise edge-disjoint trees T ₁, T ₂, …, T _l in G such that S ? V (T _i ) for 1 ? i ? l. In this paper we prove that for any two connected graphs G and H we have λ ₃(G □ H) ? λ ₃(G) + λ ₃(H), where G □ H is the Cartesian product of G and H. Moreover, the bound is sharp. We also obtain the precise values for the generalized 3-edge-connectivity of the Cartesian product of some special graph classes.     

On DP-coloring of graphs and multigraphs

While solving a question on the list coloring of planar graphs, Dvo?ák and Postle introduced the new notion of DP-coloring (they called it correspondence coloring). A DP-coloring of a graph G reduces the problem of finding a coloring of G from a given list L to the problem of finding a “large” independent set in the auxiliary graph H(G,L) with vertex set {(v, c): v ∈ V (G) and c ∈ L(v)}. It is similar to the old reduction by Plesnevi? and Vizing of the k-coloring problem to the problem of finding an independent set of size |V(G)| in the Cartesian product G□K _k, but DP-coloring seems more promising and useful than the Plesnevi?–Vizing reduction. Some properties of the DP-chromatic number χ _DP (G) resemble the properties of the list chromatic number χ _l (G) but some differ quite a lot. It is always the case that χ _DP (G) ≥ χ _l (G). The goal of this note is to introduce DP-colorings for multigraphs and to prove for them an analog of the result of Borodin and Erd?s–Rubin–Taylor characterizing the multigraphs that do not admit DP-colorings from some DP-degree-lists. This characterization yields an analog of Gallai’s Theorem on the minimum number of edges in n-vertex graphs critical with respect to DP-coloring.     

Improved Upper Bound for Generalized Acyclic Chromatic Number of Graphs

A vertex coloring of a graph G is called r-acyclic if it is a proper vertex coloring such that every cycle D receives at least min{|D|, r} colors. The r-acyclic chromatic number of G is the least number of colors in an r-acyclic coloring of G. We prove that for any number r ≥ 4, the r-acyclic chromatic number of any graph G with maximum degree Δ ≥ 7 and with girth at least (r ? 1)Δ is at most (4r ? 3)Δ.     

Independence numbers of random subgraphs of distance graphs

We consider the distance graph G(n, r, s), whose vertices can be identified with r-element subsets of the set {1, 2,..., n}, two arbitrary vertices being joined by an edge if and only if the cardinality of the intersection of the corresponding subsets is s. For s = 0, such graphs are known as Kneser graphs. These graphs are closely related to the Erd?s–Ko–Rado problem and also play an important role in combinatorial geometry and coding theory. We study some properties of random subgraphs of G(n, r, s) in the Erd?s–Rényi model, in which every edge occurs in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G(n, r, s) for the case of constant r and s. The independence number of a random subgraph is Θ(log₂n) times as large as that of the graph G(n, r, s) itself for r ≤ 2s + 1, while for r > 2s + 1 one has asymptotic stability: the two independence numbers asymptotically coincide.     

Minimum Difference Representations of Graphs

Define a k-minimum-difference-representation (k-MDR) of a graph G to be a family of sets \({\{S(v): v\in V(G)\}}\) such that u and v are adjacent in G if and only if min{|S(u)?S(v)|, |S(v)?S(u)|} ≥ k. Define ρ _min(G) to be the smallest k for which G has a k-MDR. In this note, we show that {ρ _min(G)} is unbounded. In particular, we prove that for every k there is an n ₀ such that for n > n ₀ ‘almost all’ graphs of order n satisfy ρ _min(G) > k. As our main tool, we prove a Ramsey-type result on traces of hypergraphs.     

Extendability of Contractible Configurations for Nowhere-Zero Flows and Modulo Orientations

Let H be a connected graph and G be a supergraph of H. It is trivial that for any k-flow (D, f) of G, the restriction of (D, f) on the edge subset E(G / H) is a k-flow of the contracted graph G / H. However, the other direction of the question is neither trivial nor straightforward at all: for any k-flow \((D',f')\) of the contracted graph G / H, whether or not the supergraph G admits a k-flow (D, f) that is consistent with \((D',f')\) in the edge subset E(G / H). In this paper, we will investigate contractible configurations and their extendability for integer flows, group flows, and modulo orientations. We show that no integer flow contractible graphs are extension consistent while some group flow contractible graphs are also extension consistent. We also show that every modulo \((2k+1)\)-orientation contractible configuration is also extension consistent and there are no modulo (2k)-orientation contractible graphs.     

Decomposing Oriented Graphs into Six Locally Irregular Oriented Graphs

An undirected graph G is locally irregular if every two of its adjacent vertices have distinct degrees. We say that G is decomposable into k locally irregular graphs if there exists a partition \(E_1 \cup E_2 \cup \cdots \cup E_k\) of the edge set E(G) such that each \(E_i\) induces a locally irregular graph. It was recently conjectured by Baudon et al. that every undirected graph admits a decomposition into at most three locally irregular graphs, except for a well-characterized set of indecomposable graphs. We herein consider an oriented version of this conjecture. Namely, can every oriented graph be decomposed into at most three locally irregular oriented graphs, i.e. whose adjacent vertices have distinct outdegrees? We start by supporting this conjecture by verifying it for several classes of oriented graphs. We then prove a weaker version of this conjecture. Namely, we prove that every oriented graph can be decomposed into at most six locally irregular oriented graphs. We finally prove that even if our conjecture were true, it would remain NP-complete to decide whether an oriented graph is decomposable into at most two locally irregular oriented graphs.