Longest increasing subsequences of random colored permutations.
Longest induced cycles in circulant graphs.
Loop characters
A survey of the basic results of loop characters is given on the lines of the treatment of the author and J.D.H. Smith for characters of quasigroups, including some recent deveploments. One of the successes of the theory has been its suggestive influence on the theory of association schemes, group representations and the theory of the group determinant, and selected results arising are described. A section is devoted to an explanation of how the tool of loop characters has not yet been as startlingly...
Loop-erased random walks, spanning trees and Hamiltonian cycles.
Loose Hamilton cycles in random 3-uniform hypergraphs.
Loose Hamilton cycles in random uniform hypergraphs.
Looseness and Independence Number of Triangulations on Closed Surfaces
The looseness of a triangulation G on a closed surface F2, denoted by ξ (G), is defined as the minimum number k such that for any surjection c : V (G) → {1, 2, . . . , k + 3}, there is a face uvw of G with c(u), c(v) and c(w) all distinct. We shall bound ξ (G) for triangulations G on closed surfaces by the independence number of G denoted by α(G). In particular, for a triangulation G on the sphere, we have [...] and this bound is sharp. For a triangulation G on a non-spherical surface F2, we have...
Low rank co-diagonal matrices and Ramsey graphs.
Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and coloring.
Low-Degree Minimum Spanning Trees.
Low-distortion embeddings of trees.
Lower bound for the norm of a vertex-transitive graph.
Lower bound for the size of maximal nontraceable graphs.
Lower bound on the distance -domination number of a tree
Lower bound on the domination number of a tree
>We prove that the domination number γ(T) of a tree T on n ≥ 3 vertices and with n₁ endvertices satisfies inequality γ(T) ≥ (n+2-n₁)/3 and we characterize the extremal graphs.
Lower Bounds for Estrada Index
Lower bounds for integral functionals generated by bipartite graphs
We study lower estimates for integral fuctionals for which the structure of the integrand is defined by a graph, in particular, by a bipartite graph. Functionals of such kind appear in statistical mechanics and quantum chemistry in the context of Mayer's transformation and Mayer's cluster integrals. Integral functionals generated by graphs play an important role in the theory of graph limits. Specific kind of functionals generated by bipartite graphs are at the center of the famous and much studied...
Lower bounds for the average genus of a CF-graph.
Lower bounds for the colored mixed chromatic number of some classes of graphs
A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph is defined as the smallest order of a colored mixed graph such that there exists a (color preserving) homomorphism from to . These notions were introduced by Nešetřil and Raspaud in Colored homomorphisms of colored mixed graphs, J. Combin. Theory Ser. B 80 (2000), no. 1, 147–155, where the exact chromatic number of colored mixed trees was given. We prove here that this chromatic...
Lower bounds for the domination number
In this note, we prove several lower bounds on the domination number of simple connected graphs. Among these are the following: the domination number is at least two-thirds of the radius of the graph, three times the domination number is at least two more than the number of cut-vertices in the graph, and the domination number of a tree is at least as large as the minimum order of a maximal matching.