The lattice of threshold graphs.
The leafage of a chordal graph
The leafage l(G) of a chordal graph G is the minimum number of leaves of a tree in which G has an intersection representation by subtrees. We obtain upper and lower bounds on l(G) and compute it on special classes. The maximum of l(G) on n-vertex graphs is n - lg n - 1/2 lg lg n + O(1). The proper leafage l*(G) is the minimum number of leaves when no subtree may contain another; we obtain upper and lower bounds on l*(G). Leafage equals proper leafage on claw-free chordal graphs. We use asteroidal...
The least connected non-vertex-transitive graph with constant neighbourhoods
The Least Eigenvalue of Graphs whose Complements Are Uni- cyclic
A graph in a certain graph class is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum among all graphs in that class. Bell et al. have identified a subclass within the connected graphs of order n and size m in which minimizing graphs belong (the complements of such graphs are either disconnected or contain a clique of size n/2 ). In this paper we discuss the minimizing graphs of a special class of graphs of order n whose complements are connected and contains...
The lifted root number conjecture for fields of prime degree over the rationals: an approach via trees and Euler systems
The so-called Lifted Root Number Conjecture is a strengthening of Chinburg’s - conjecture for Galois extensions of number fields. It is certainly more difficult than the -localization. Following the lead of Ritter and Weiss, we prove the Lifted Root Number Conjecture for the case that and the degree of is an odd prime, with another small restriction on ramification. The very explicit calculations with cyclotomic units use trees and some classical combinatorics for bookkeeping. An important...
The linear arboricity of -regular graphs
The linear complexity of a graph.
The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs
A distinguishing coloring of a graph G is a coloring of the vertices so that every nontrivial automorphism of G maps some vertex to a vertex with a different color. The distinguishing number of G is the minimum k such that G has a distinguishing coloring where each vertex is assigned a color from {1, . . . , k}. A list assignment to G is an assignment L = {L(v)}v∈V (G) of lists of colors to the vertices of G. A distinguishing L-coloring of G is a distinguishing coloring of G where the color of each...
The list linear arboricity of planar graphs
The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. An and Wu introduce the notion of list linear arboricity lla(G) of a graph G and conjecture that lla(G) = la(G) for any graph G. We confirm that this conjecture is true for any planar graph having Δ ≥ 13, or for any planar graph with Δ ≥ 7 and without i-cycles for some i ∈ {3,4,5}. We also prove that ⌈½Δ(G)⌉ ≤ lla(G) ≤ ⌈½(Δ(G)+1)⌉ for any planar graph having Δ ≥ 9.
The local metric dimension of a graph
For an ordered set of distinct vertices in a nontrivial connected graph , the metric code of a vertex of with respect to is the -vector where is the distance between and for . The set is a local metric set of if for every pair of adjacent vertices of . The minimum positive integer for which has a local metric -set is the local metric dimension of . A local metric set of of cardinality is a local metric basis of . We characterize all nontrivial connected...
The Loebl-Komlós-Sós conjecture for trees of diameter 5 and for certain caterpillars.
The lollipop graph is determined by its spectrum.
The lonely runner with seven runners.
The lower tail of the random minimum spanning tree.
The MacNeille completion of the poset of partial injective functions.
The main part of the spectrum, divisors and switching of graphs.
The map asymptotics constant .
The Markov chain asymptotics of random mapping graphs
The matching polynomial of a distance-regular graph.
The Mathieu group and its pseudogroup extension .