We consider the number of spanning trees in circulant graphs of ${\it\beta}n$ vertices with generators depending linearly on $n$. The matrix tree theorem gives a closed formula of ${\it\beta}n$ factors, while we derive a formula of ${\it\beta}-1$ factors. We also derive a formula for the number of spanning trees in discrete tori. Finally, we compare the spanning tree entropy of circulant graphs with fixed and nonfixed generators.

We give an easy method for constructing containers for simple hypergraphs. The method also has consequences for non-simple hypergraphs. Some applications are given; in particular, a very transparent calculation is offered for the number of H-free hypergraphs, where H is some fixed uniform hypergraph.

We study the isomorphism problem of vertex-transitive cubic graphs which have a transitive simple group of automorphisms.

We study 3-random-like graphs, that is, sequences of graphs in which the densities of triangles and anti-triangles converge to 1/8. Since the random graph $\mathcal{G}$n,1/2 is, in particular, 3-random-like, this can be viewed as a weak version of quasi-randomness. We first show that 3-random-like graphs are 4-universal, that is, they contain induced copies of all 4-vertex graphs. This settles a question of Linial and Morgenstern [10]. We then show that for larger subgraphs, 3-random-like sequences demonstrate completely different behaviour. We prove that for every graph H on n ⩾ 13 vertices there exist 3-random-like graphs without an induced copy of H. Moreover, we prove that for every ℓ there are 3-random-like graphs which are ℓ-universal but not m-universal when m is sufficiently large compared to ℓ.

In 1981 Beck and Fiala proved an upper bound for the discrepancy of a set system of degree d that is independent of the size of the ground set. In the intervening years the bound has been decreased from 2d − 2 to 2d − 4. We improve the bound to 2d − log*d.

The Teter, Payne, and Allan “preconditioning” function plays a significant role in planewave DFT calculations. This function is often called the TPA preconditioner. We present a detailed study of this “preconditioning” function. We develop a general formula that can readily generate a class of “preconditioning” functions. These functions have higher order approximation accuracy and fulfill the two essential “preconditioning” purposes as required in planewave DFT calculations. Our general class of functions are expected to have applications in other areas.

The discrete Green's function (without boundary) $\mathbb{G}$ is a pseudo-inverse of the combinatorial Laplace operator of a graph G = (V, E). We reveal the intimate connection between Green's function and the theory of exact stopping rules for random walks on graphs. We give an elementary formula for Green's function in terms of state-to-state hitting times of the underlying graph. Namely,$\mathbb{G}(i,j) = \pi_j \bigl( H(\pi,j) - H(i,j) \bigr),$ where πi is the stationary distribution at vertex i, H(i, j) is the expected hitting time for a random walk starting from vertex i to first reach vertex j, and H(π, j) = ∑k∈V πkH(k, j). This formula also holds for the digraph Laplace operator.

The most important characteristics of a stopping rule are its exit frequencies, which are the expected number of exits of a given vertex before the rule halts the walk. We show that Green's function is, in fact, a matrix of exit frequencies plus a rank one matrix. In the undirected case, we derive spectral formulas for Green's function and for some mixing measures arising from stopping rules. Finally, we further explore the exit frequency matrix point of view, and discuss a natural generalization of Green's function for any distribution τ defined on the vertex set of the graph.

We consider large random graphs with prescribed degrees, as generated by the configuration model. In the regime where the empirical degree distribution approaches a limit μ with finite mean, we establish the systematic convergence of a broad class of graph parameters that includes the independence number, the maximum cut size, the logarithm of the Tutte polynomial, and the free energy of the anti-ferromagnetic Ising and Potts models. Contrary to previous works, our results are not a priori limited to the free energy of some prescribed graphical model. They apply more generally to any additive, Lipschitz and concave graph parameter. In addition, the corresponding limits are shown to be Lipschitz and concave in the degree distribution μ. This considerably extends the applicability of the celebrated interpolation method, introduced in the context of spin glasses, and recently related to the challenging question of right-convergence of sparse graphs.

We investigate topological realizations of higher-rank graphs. We show that the fundamental group of a higher-rank graph coincides with the fundamental group of its topological realization. We also show that topological realization of higher-rank graphs is a functor and that for each higher-rank graph Λ, this functor determines a category equivalence between the category of coverings of Λ and the category of coverings of its topological realization. We discuss how topological realization relates to two standard constructions for k-graphs: projective limits and crossed products by finitely generated free abelian groups.

The classical first and second Zagreb indices of a graph $G$ are defined as $M_{1}(G)=\sum _{v\in V(G)}d(v)^{2}$ and $M_{2}(G)=\sum _{e=uv\in E(G)}d(u)d(v),$ where $d(v)$ is the degree of the vertex $v$ of $G.$ Recently, Furtula et al. [‘On difference of Zagreb indices’, Discrete Appl. Math.178 (2014), 83–88] studied the difference of $M_{1}$ and $M_{2},$ and showed that this difference is closely related to the vertex-degree-based invariant $RM_{2}(G)=\sum _{e=uv\in E(G)}[d(u)-1][d(v)-1]$, the reduced second Zagreb index. In this paper, we present sharp bounds for the reduced second Zagreb index, given the matching number, independence number and vertex connectivity, and we also completely determine the extremal graphs.

We deal with a random graph model evolving in discrete time steps by duplicating and deleting the edges of randomly chosen vertices. We prove the existence of an almost surely asymptotic degree distribution, with stretched exponential decay; more precisely, the proportion of vertices of degree d tends to some positive number cd > 0 almost surely as the number of steps goes to ∞, and cd ~ (eπ)1/2d1/4e-2√d holds as d → ∞.

In this paper we investigate first passage percolation on an inhomogeneous random graph model introduced by Bollobás et al. (2007). Each vertex in the graph has a type from a type space, and edge probabilities are independent, but depend on the types of the end vertices. Each edge is given an independent exponential weight. We determine the distribution of the weight of the shortest path between uniformly chosen vertices in the giant component and show that the hopcount, i.e. the number of edges on this minimal-weight path, properly normalized, follows a central limit theorem. We handle the cases where the average number of neighbors λ̃n of a vertex tends to a finite λ̃ in full generality and consider λ̃ = ∞ under mild assumptions. This paper is a generalization of the paper of Bhamidi et al. (2011), where first passage percolation is explored on the Erdős-Rényi graphs.

We consider Euclidean first passage percolation on a large family of connected random geometric graphs in the d-dimensional Euclidean space encompassing various well-known models from stochastic geometry. In particular, we establish a strong linear growth property for shortest-path lengths on random geometric graphs which are generated by point processes. We consider the event that the growth of shortest-path lengths between two (end) points of the path does not admit a linear upper bound. Our linear growth property implies that the probability of this event tends to zero sub-exponentially fast if the direct (Euclidean) distance between the endpoints tends to infinity. Besides, for a wide class of stationary and isotropic random geometric graphs, our linear growth property implies a shape theorem for the Euclidean first passage model defined by such random geometric graphs. Finally, this shape theorem can be used to investigate a problem which is considered in structural analysis of fixed-access telecommunication networks, where we determine the limiting distribution of the length of the longest branch in the shortest-path tree extracted from a typical segment system if the intensity of network stations converges to 0.

Vertices arrive sequentially in space and are joined to existing vertices at random according to a preferential rule combining degree and spatial proximity. We investigate phase transitions in the resulting graph as the relative strengths of these two components of the attachment rule are varied.

Previous work of one of the authors showed that when the geometric component is weak, the limiting degree sequence mimics the standard Barabási-Albert preferential attachment model. We show that at the other extreme, in the case of a sufficiently strong geometric component, the limiting degree sequence mimics a purely geometric model, the on-line nearest-neighbour graph, for which we prove some extensions of known results. We also show the presence of an intermediate regime, with behaviour distinct from both the on-line nearest-neighbour graph and the Barabási-Albert model; in this regime, we obtain a stretched exponential upper bound on the degree sequence.

For two given graphs $G_{1}$ and $G_{2}$, the Ramsey number $R(G_{1},G_{2})$ is the smallest integer $N$ such that, for any graph $G$ of order $N$, either $G$ contains $G_{1}$ as a subgraph or the complement of $G$ contains $G_{2}$ as a subgraph. A fan $F_{l}$ is $l$ triangles sharing exactly one vertex. In this note, it is shown that $R(F_{n},F_{m})=4n+1$ for $n\geq \max \{m^{2}-m/2,11m/2-4\}$.

Lladó and Moragas [‘Cycle-magic graphs’, Discrete Math.307 (2007), 2925–2933] showed the cyclic-magic and cyclic-supermagic behaviour of several classes of connected graphs. They discussed cycle-magic labellings of subdivided wheels and friendship graphs, but there are no further results on cycle-magic labellings of other families of subdivided graphs. In this paper, we find cycle-magic labellings for subdivided graphs. We show that if a graph has a cycle-(super)magic labelling, then its uniform subdivided graph also has a cycle-(super)magic labelling. We also discuss some cycle-supermagic labellings for nonuniform subdivided fans and triangular ladders.

The total irregularity of a simple undirected graph $G$ is defined as $\text{irr}_{t}(G)=\frac{1}{2}\sum _{u,v\in V(G)}|d_{G}(u)-d_{G}(v)|$, where $d_{G}(u)$ denotes the degree of a vertex $u\in V(G)$. Obviously, $\text{irr}_{t}(G)=0$ if and only if $G$ is regular. Here, we characterise the nonregular graphs with minimal total irregularity and thereby resolve the recent conjecture by Zhu et al. [‘The minimal total irregularity of graphs’, Preprint, 2014, arXiv:1404.0931v1 ] about the lower bound on the minimal total irregularity of nonregular connected graphs. We show that the conjectured lower bound of $2n-4$ is attained only if nonregular connected graphs of even order are considered, while the sharp lower bound of $n-1$ is attained by graphs of odd order. We also characterise the nonregular graphs with the second and the third smallest total irregularity.

This paper addresses the following question for a given graph H: What is the minimum number f(H) such that every graph with average degree at least f(H) contains H as a minor? Due to connections with Hadwiger's conjecture, this question has been studied in depth when H is a complete graph. Kostochka and Thomason independently proved that $f(K_t)=ct\sqrt{\ln t}$. More generally, Myers and Thomason determined f(H) when H has a super-linear number of edges. We focus on the case when H has a linear number of edges. Our main result, which complements the result of Myers and Thomason, states that if H has t vertices and average degree d at least some absolute constant, then $f(H)\leq 3.895\sqrt{\ln d}\,t$. Furthermore, motivated by the case when H has small average degree, we prove that if H has t vertices and q edges, then f(H) ⩽ t + 6.291q (where the coefficient of 1 in the t term is best possible).

Let h > w > 0 be two fixed integers. Let H be a random hypergraph whose hyperedges are all of cardinality h. To w-orient a hyperedge, we assign exactly w of its vertices positive signs with respect to the hyperedge, and the rest negative signs. A (w,k)-orientation of H consists of a w-orientation of all hyperedges of H, such that each vertex receives at most k positive signs from its incident hyperedges. When k is large enough, we determine the threshold of the existence of a (w,k)-orientation of a random hypergraph. The (w,k)-orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. The graph case, when h = 2 and w = 1, was solved recently by Cain, Sanders and Wormald and independently by Fernholz and Ramachandran. This settled a conjecture of Karp and Saks.

Let $\mathcal{F}$ be a family of r-uniform hypergraphs. The chromatic threshold of $\mathcal{F}$ is the infimum of all non-negative reals c such that the subfamily of $\mathcal{F}$ comprising hypergraphs H with minimum degree at least $c \binom{| V(H) |}{r-1}$ has bounded chromatic number. This parameter has a long history for graphs (r = 2), and in this paper we begin its systematic study for hypergraphs.

Łuczak and Thomassé recently proved that the chromatic threshold of the so-called near bipartite graphs is zero, and our main contribution is to generalize this result to r-uniform hypergraphs. For this class of hypergraphs, we also show that the exact Turán number is achieved uniquely by the complete (r + 1)-partite hypergraph with nearly equal part sizes. This is one of very few infinite families of non-degenerate hypergraphs whose Turán number is determined exactly. In an attempt to generalize Thomassen's result that the chromatic threshold of triangle-free graphs is 1/3, we prove bounds for the chromatic threshold of the family of 3-uniform hypergraphs not containing {abc, abd, cde}, the so-called generalized triangle.

In order to prove upper bounds we introduce the concept of fibre bundles, which can be thought of as a hypergraph analogue of directed graphs. This leads to the notion of fibre bundle dimension, a structural property of fibre bundles that is based on the idea of Vapnik–Chervonenkis dimension in hypergraphs. Our lower bounds follow from explicit constructions, many of which use a hypergraph analogue of the Kneser graph. Using methods from extremal set theory, we prove that these Kneser hypergraphs have unbounded chromatic number. This generalizes a result of Szemerédi for graphs and might be of independent interest. Many open problems remain.