In this paper, we give the sharp upper bound for the number of vertices with positive curvature in a planar graph with nonnegative combinatorial curvature. Based on this, we show that the automorphism group of a planar—possibly infinite—graph with nonnegative combinatorial curvature and positive total curvature is a finite group, and give an upper bound estimate for the order of the group.

We investigate quantum graphs with infinitely many vertices and edges without the common restriction on the geometry of the underlying metric graph that there is a positive lower bound on the lengths of its edges. Our central result is a close connection between spectral properties of a quantum graph and the corresponding properties of a certain weighted discrete Laplacian on the underlying discrete graph. Using this connection together with spectral theory of (unbounded) discrete Laplacians on infinite graphs, we prove a number of new results on spectral properties of quantum graphs. Namely, we prove several self-adjointness results including a Gaffney-type theorem. We investigate the problem of lower semiboundedness, prove several spectral estimates (bounds for the bottom of spectra and essential spectra of quantum graphs, CLR-type estimates) and study spectral types.

Let $K_k$, $C_k$, $T_k$, and $P_{k}$ denote a complete graph on $k$ vertices, a cycle on $k$ vertices, a tree on $k+1$ vertices, and a path on $k+1$ vertices, respectively. Let $K_{m}-H$ be the graph obtained from $K_{m}$ by removing the edges set $E(H)$ of the graph $H$ ($H$ is a subgraph of $K_{m}$). A sequence $S$ is potentially $K_{m}-H$-graphical if it has a realization containing a $K_{m}-H$ as a subgraph. Let $\sigma(K_{m}-H, n)$ denote the smallest degree sum such that every $n$-term graphical sequence $S$ with $\sigma(S)\geq \sigma(K_{m}-H, n)$ is potentially $K_{m}-H$-graphical. In this paper, we determine the values of $\sigma (K_{r+1}-H, n)$ for $n\geq 4r+10, r\geq 3, r+1 \geq k \geq 4$ where $H$ is a graph on $k$ vertices which contains a tree on $4$ vertices but not contains a cycle on $3$ vertices. We also determine the values of $\sigma (K_{r+1}-P_2, n)$ for $n\geq 4r+8, r\geq 3$.

We prove a Harnack inequality for Dirichlet eigenfunctions of abelian homogeneous graphs and their convex subgraphs. We derive lower bounds for Dirichlet eigenvalues using the Harnack inequality. We also consider a randomization problem in connection with combinatorial games using Dirichlet eigenvalues. 2000 John Wiley & Sons, Inc. J Graph Theory 34: 247257, 2000

We study the cluster combinatorics of d-cluster tilting objects in d-cluster categories. Using mutations of maximal rigid objects in d-cluster categories, which are defined in a similar way to mutations for d-cluster tilting objects, we prove the equivalences between d-cluster tilting objects, maximal rigid objects and complete rigid objects. Using the chain of d+1 triangles of d-cluster tilting objects in [O. Iyama, Y. Yoshino, Mutations in triangulated categories and rigid Cohen–Macaulay modules, Invent. Math. 172 (1) (2008) 117–168], we prove that any almost complete d-cluster tilting object has exactly d+1 complements, compute the extension groups between these complements, and study the middle terms of these d+1 triangles. All results are the extensions of corresponding results on cluster tilting objects in cluster categories established for d-cluster categories in [A. Buan, R. Marsh, M. Reineke, I. Reiten, G. Todorov, Tilting theory and cluster combinatorics, Adv. Math. 204 (2006) 572–618]. They are applied to the Fomin–Reading generalized cluster complexes of finite root systems defined and studied in [S. Fomin, N. Reading, Generalized cluster complexes and Coxeter combinatorics, Int. Math. Res. Not. 44 (2005) 2709–2757; H. Thomas, Defining an m-cluster category, J. Algebra 318 (2007) 37–46; K. Baur, R. Marsh, A geometric description of m-cluster categories, Trans. Amer. Math. Soc. 360 (2008) 5789–5803; K. Baur, R. Marsh, A geometric description of the m-cluster categories of type D_n, preprint, arXiv:math.RT/0610512; see also Int. Math. Res. Not. 2007 (2007), doi:10.1093/imrn/rnm011], and to that of infinite root systems [B. Zhu, Generalized cluster complexes via quiver representations, J. Algebraic Combin. 27 (2008) 25–54].