Sharp threshold functions for random intersection graphs via a coupling method.
Sharp Upper Bounds for Generalized Edge-Connectivity of Product Graphs
The generalized k-connectivity κk(G) of a graph G was introduced by Hager in 1985. 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) denote the maximum number ℓ of pairwise edge-disjoint trees T1, T2, . . . , Tℓ in G such that S ⊆ V (Ti) for 1 ≤ i ≤ ℓ. In this paper, we study the generalized edge- connectivity of product graphs and obtain sharp upper bounds...
Sharp Upper Bounds on the Signless Laplacian Spectral Radius of Strongly Connected Digraphs
Let G = (V (G),E(G)) be a simple strongly connected digraph and q(G) be the signless Laplacian spectral radius of G. For any vertex vi ∈ V (G), let d+i denote the outdegree of vi, m+i denote the average 2-outdegree of vi, and N+i denote the set of out-neighbors of vi. In this paper, we prove that: (1) (1) q(G) = d+1 +d+2 , (d+1 ≠ d+2) if and only if G is a star digraph [...] ,where d+1, d+2 are the maximum and the second maximum outdegree, respectively [...] is the digraph on n vertices obtained...
Sharp upper bounds on the spectral radius of the Laplacian matrix of graphs.
Sharply transitive 1-factorizations of complete multipartite graphs.
Shields-Harary numbers of graphs with respect to continuous concave cost functions.
Shifted set families, degree sequences, and plethysm.
Short certificates for tournaments.
Short cycles in digraphs with local average outdegree at least two.
Short cycles in random regular graphs.
Short cycles of low weight in normal plane maps with minimum degree 5
In this note, precise upper bounds are determined for the minimum degree-sum of the vertices of a 4-cycle and a 5-cycle in a plane triangulation with minimum degree 5: w(C₄) ≤ 25 and w(C₅) ≤ 30. These hold because a normal plane map with minimum degree 5 must contain a 4-star with . These results answer a question posed by Kotzig in 1979 and recent questions of Jendrol’ and Madaras.
Short paths in 3-uniform quasi-random hypergraphs
Frankl and Rödl [3] proved a strong regularity lemma for 3-uniform hypergraphs, based on the concept of δ-regularity with respect to an underlying 3-partite graph. In applications of that lemma it is often important to be able to "glue" together separate pieces of the desired subhypergraph. With this goal in mind, in this paper it is proved that every pair of typical edges of the underlying graph can be connected by a hyperpath of length at most seven. The typicality of edges is defined in terms...
Short score certificates for upset tournaments.
Shortness coefficient of cyclically 5-connected cubic planar graphs.
Shortness coefficient of cyclically 5-connected cubic planar graphs. (Short Communication).
Sierpiński graphs as spanning subgraphs of Hanoi graphs
Hanoi graphs H pn model the Tower of Hanoi game with p pegs and n discs. Sierpinski graphs S pn arose in investigations of universal topological spaces and have meanwhile been studied extensively. It is proved that S pn embeds as a spanning subgraph into H pn if and only if p is odd or, trivially, if n = 1.
Sign patterns that allow eventual positivity.
Sign patterns that require eventual positivity or require eventual nonnegativity.
Sign patterns that require or allow power-positivity.
Signed 2-domination in caterpillars
A caterpillar is a tree with the property that after deleting all its vertices of degree 1 a simple path is obtained. The signed 2-domination number and the signed total 2-domination number of a graph are variants of the signed domination number and the signed total domination number . Their values for caterpillars are studied.