Recent zbMATH articles in MSC 05C30 https://www.zbmath.org/atom/cc/05C30 2021-04-16T16:22:00+00:00 Werkzeug The component counts of random injections. https://www.zbmath.org/1456.05004 2021-04-16T16:22:00+00:00 "Stark, Dudley" https://www.zbmath.org/authors/?q=ai:stark.dudley Summary: A model of random injections is defined which has domain $$A\cup B$$ and codomain $$A\cup C$$, where $$A, B$$ and $$C$$ are mutually disjoint finite sets such that $$|B|\leqslant |C|$$. The model encompasses both random permutations, which is the case $$B=C=\emptyset$$, and random maximum matchings of a complete bipartite graph, which is the case $$A=\emptyset$$. The possible components of random injections are cycles and paths. Results on the counts of cycles and paths of different sizes are obtained for this model. On the sum of $$k$$ largest Laplacian eigenvalues of a graph and clique number. https://www.zbmath.org/1456.05104 2021-04-16T16:22:00+00:00 "Ganie, Hilal A." https://www.zbmath.org/authors/?q=ai:ganie.hilal-ahmad "Pirzada, S." https://www.zbmath.org/authors/?q=ai:pirzada.shariefuddin "Trevisan, Vilmar" https://www.zbmath.org/authors/?q=ai:trevisan.vilmar Summary: For a simple graph $$G$$ with order $$n$$ and size $$m$$ having Laplacian eigenvalues $$\mu_1, \mu_2, \dots, \mu_{n-1},\mu_n=0$$, let $$S_k(G)=\sum_{i=1}^k\mu_i$$, be the sum of $$k$$ largest Laplacian eigenvalues of $$G$$. We obtain upper bounds for the sum of $$k$$ largest Laplacian eigenvalues of two large families of graphs. As a consequence, we prove Brouwer's Conjecture for large number of graphs which belong to these families of graphs. On the number of weakly connected subdigraphs in random $$k$$NN digraphs. https://www.zbmath.org/1456.05079 2021-04-16T16:22:00+00:00 "Bahadır, Selim" https://www.zbmath.org/authors/?q=ai:bahadir.selim "Ceyhan, Elvan" https://www.zbmath.org/authors/?q=ai:ceyhan.elvan Summary: We study the number of copies of a weakly connected subdigraph of the $$k$$ nearest neighbor $$(k$$NN) digraph based on data from certain random point processes in $$\mathbb{R}^d$$. In particular, based on the asymptotic theory for functionals of point sets from homogeneous Poisson process (HPP) and uniform binomial process (UBP), we provide a general result for the asymptotic behavior of the number of weakly connected subdigraphs of $$k$$ NN digraphs. As corollaries, we obtain asymptotic results for the number of vertices with fixed indegree, the number of shared $$k$$NN pairs, and the number of reflexive $$k$$NNs in the $$k$$NN digraph based on data from HPP and UBP. We also provide several extensions of our results pertaining to the $$k$$NN digraphs; more specifically, the results are extended to the number of weakly connected subdigraphs in a digraph based only on a subset of the first $$k$$NNs, and in a marked or labeled digraph where each vertex also has a mark or a label associated with it, and also to the number of subgraphs of the underlying $$k$$NN graphs. These constructs derived from $$k$$NN digraphs, $$k$$NN graphs, and the marked/labeled $$k$$NN graphs have applications in various fields such as pattern classification and spatial data analysis, and our extensions provide the theoretical basis for certain tools in these areas. Many cliques with few edges. https://www.zbmath.org/1456.05080 2021-04-16T16:22:00+00:00 "Kirsch, Rachel" https://www.zbmath.org/authors/?q=ai:kirsch.rachel "Radcliffe, A. J." https://www.zbmath.org/authors/?q=ai:radcliffe.andrew-john Summary: Recently \textit{J. Cutler} and \textit{A. J. Radcliffe} [The maximum number of complete subgraphs in a graph with given maximum degree'', Preprint, \url{arXiv:1306.1803}] proved that the graph on $$n$$ vertices with maximum degree at most $$r$$ having the most cliques is a disjoint union of $$\lfloor n/(r+1)\rfloor$$ cliques of size $$r+1$$ together with a clique on the remainder of the vertices. It is very natural also to consider this question when the limiting resource is edges rather than vertices. In this paper we prove that among graphs with $$m$$ edges and maximum degree at most $$r$$, the graph that has the most cliques of size at least two is the disjoint union of $$\bigl\lfloor m \bigm/\binom{r+1}{2} \bigr\rfloor$$ cliques of size $$r+1$$ together with the colex graph using the remainder of the edges. The 3-edge-colouring problem on the 4-8 and 3-12 lattices. https://www.zbmath.org/1456.82127 2021-04-16T16:22:00+00:00 "Fjærestad, J. O." https://www.zbmath.org/authors/?q=ai:fjaerestad.john-ove Enumeration of spanning trees on Apollonian networks. https://www.zbmath.org/1456.05161 2021-04-16T16:22:00+00:00 "Zhang, Jingyuan" https://www.zbmath.org/authors/?q=ai:zhang.jingyuan "Sun, Weigang" https://www.zbmath.org/authors/?q=ai:sun.weigang "Xu, Guanghui" https://www.zbmath.org/authors/?q=ai:xu.guanghui Using edge generating function to solve monomer-dimer problem. https://www.zbmath.org/1456.05008 2021-04-16T16:22:00+00:00 "Xin, Guoce" https://www.zbmath.org/authors/?q=ai:xin.guoce "Yan, Weigen" https://www.zbmath.org/authors/?q=ai:yan.weigen Summary: It is well known that the monomer-dimer problem is very interesting but difficult in statistical physics, which is equivalent to the enumerative problem of matchings of a graph in combinatorics. In this paper, using the generating function of edge subsets of a graph, we obtain the solution of the monomer-dimer problem of a number of graphs. Multicritical continuous random trees. https://www.zbmath.org/1456.82431 2021-04-16T16:22:00+00:00 "Bouttier, J." https://www.zbmath.org/authors/?q=ai:bouttier.jeremie "Di Francesco, P." https://www.zbmath.org/authors/?q=ai:di-francesco.philippe "Guitter, E." https://www.zbmath.org/authors/?q=ai:guitter.emmanuel Pattern occurrences in random planar maps. https://www.zbmath.org/1456.05144 2021-04-16T16:22:00+00:00 "Drmota, Michael" https://www.zbmath.org/authors/?q=ai:drmota.michael "Stufler, Benedikt" https://www.zbmath.org/authors/?q=ai:stufler.benedikt Summary: We consider planar maps adjusted with a (regular critical) Boltzmann distribution and show that the expected number of pattern occurrences of a given map is asymptotically linear when the number $$n$$ of edges goes to infinity. The main ingredient for the proof is an extension of a formula by \textit{V. A. Liskovets} [J. Comb. Theory, Ser. B 75, No. 1, 116--133 (1999; Zbl 0930.05050)].