Search

Given an undirected multigraph G = (V , E) with no self-loops, and one of its nodes s ∈ V , we consider the #P-complete problem of counting the number E T s (e) (G) of its Eulerian tours starting and ending at node s. We provide lower and upper bounds on the size of E T s (e) (G) . Namely, let d(v) denote the degree of a node v ∈ V ; we show that max { L 1 (e) , L 2 (e) } ≤ | E T s (e) (G) | ≤ d (s) ∏ v ∈ V (d (v) - 1) ! ! where L 1 (e) = (d (s) - 1) ! ! ∏ v ∈ V \ s (d (v) - 2) ! ! and L 2 (e) = 2 1 - | V | + | E | . We also consider the notion of node-distinct Eulerian tours. Indeed, the classical Eulerian tours are edge-distinct sequences. Node-distinct Eulerian tours, denoted E T s (n) (G) , should instead be different as node sequences. Let Δ (u) be the number of distinct neighbors of a node u, D ⊆ E be the set of distinct edges in the multigraph G, and m(e) for an edge e ∈ E be its multiplicity (i.e. | E | = ∑ e ∈ D m (e) ). We prove that max { L 1 (n) , L 2 (n) , L 3 (n) } ≤ | E T s (n) (G) | ≤ d (s) ∏ v ∈ V (d (v) - 1) ! ! · ∏ e ∈ D m (e) ! - 1 , where L 1 (n) = L 1 (e) / (∏ e ∈ D m (e) !) , L 2 (n) = (Δ (s) - 1) ! ! ∏ v ∈ V \ s (Δ (v) - 2) ! ! , and L 3 (n) = 2 1 - | V | + | D | . We also extend all of our results to graphs having self-loops. [ABSTRACT FROM AUTHOR]

In this article sets of certain subgraphs of a graph are formalized in the Mizar system [7], [1], based on the formalization of graphs in [11] briefly sketched in [12]. The main result is the spanning subgraph theorem. [ABSTRACT FROM AUTHOR]

A graph is called odd if there is an orientation of its edges and an automorphism that reverses the sense of an odd number of its edges and even otherwise. Pontus von Brömssen (né Andersson) showed that the existence of such an automorphism is independent of the orientation and considered the question of counting pairwise non-isomorphic even graphs. Based on computational evidence, he made the rather surprising conjecture that the number of pairwise non-isomorphic even graphs on n vertices is equal to the number of pairwise non-isomorphic tournaments on n vertices. We prove this conjecture using a counting argument with several applications of the Cauchy–Frobenius theorem. [ABSTRACT FROM AUTHOR]

This paper presents a general recursive formula to estimate the number of labeled graphs as well as details to evaluate the formula for the following graph properties: number of edges (graph density), degree sequence, degree distribution, classification mixing, and degree mixing, i.e., the formula estimates the number of labeled graphs that have given values for graph properties. The proposed approach can be extended to additional graph properties (e.g., number of triangles) as well as properties of bipartite graphs. For special settings in which formulas exist from previous research, simulation studies demonstrate the validity of the proposed approach. In addition, we demonstrate how our approach can be used to quantify the level of variability in values of a graph property in the subset of graphs that hold a specified value of a different graph property (or properties) constant. [ABSTRACT FROM AUTHOR]

Complex Networks can depict a clear image of real-world systems. A real-world scenario can be represented a graph with interconnected layers - called a multilayer network. Finding motifs can give an idea of the topology of complex systems and help understand the graphs’ dynamics. Looking at motifs as atoms of the network is helpful to analyze the relationship between nodes and between layers. This work suggests a sub-graph enumeration approach to find and count the motifs in a multilayer network. The proposed work has many applications in graph mining, particularly to the structure and dynamics of complex networks.

This paper proposes a new general technique for maximal subgraph enumeration which we call proximity search, whose aim is to design efficient enumeration algorithms for problems that could not be solved by existing frameworks. To support this claim and illustrate the technique we include output-polynomial algorithms for several problems for which output-polynomial algorithms were not known, including the enumeration of maximal bipartite subgraphs, maximal k-degenerate subgraphs (for bounded k), maximal induced chordal subgraphs, and maximal induced trees. Using known techniques, such as reverse search, the space of all maximal solutions induces an implicit directed graph called "solution graph" or \supergraph," and solutions are enumerated by traversing it; however, nodes in this graph can have exponential out-degree, thus requiring exponential time to be spent on each solution. The novelty of proximity search is a formalization that allows us to define a better solution graph, and a technique, which we call canonical reconstruction, by which we can exploit the properties of given problems to build such graphs. This results in solution graphs whose nodes have significantly smaller (i.e., polynomial) out-degree with respect to existing approaches, but that remain strongly connected, so that all solutions can be enumerated in polynomial delay by a traversal. A drawback of this approach is the space required to keep track of visited solutions, which can be exponential; we further propose a technique to induce a parent-child relationship among solutions and achieve polynomial space when suitable conditions are met. [ABSTRACT FROM AUTHOR]

This paper presents a general recursive formula to estimate the number of labeled graphs as well as details to evaluate the formula for the following graph properties: number of edges (graph density), degree sequence, degree distribution, classification mixing, and degree mixing, i.e., the formula estimates the number of labeled graphs that have given values for graph properties. The proposed approach can be extended to additional graph properties (e.g., number of triangles) as well as properties of bipartite graphs. For special settings in which formulas exist from previous research, simulation studies demonstrate the validity of the proposed approach. In addition, we demonstrate how our approach can be used to quantify the level of variability in values of a graph property in the subset of graphs that hold a specified value of a different graph property (or properties) constant.

In this paper we consider the problem of listing the maximal k -degenerate induced subgraphs of a chordal graph, and propose an output-sensitive algorithm using delay O (m ⋅ ω (G)) for any n -vertex chordal graph with m edges, where ω (G) ≤ n is the maximum size of a clique in G. Degeneracy is a well known sparsity measure, and k -degenerate subgraphs are a notion of sparse subgraphs, which generalizes other problems such as independent sets (0-degenerate subgraphs) and forests (1-degenerate subgraphs). Many efficient enumeration algorithms are designed by solving the so-called Extension problem , which asks whether there exists a maximal solution containing a given set of nodes, but no node from a forbidden set. We show that solving this problem is np -complete for maximal k -degenerate induced subgraphs, motivating the need for additional techniques. [ABSTRACT FROM AUTHOR]

We provide an explicit algorithm for sampling a uniform simple connected random graph with a given degree sequence. By products of this central result include: (1) continuum scaling limits of uniform simple connected graphs with given degree sequence and asymptotics for the number of simple connected graphs with given degree sequence under some regularity conditions, and (2) scaling limits for the metric space structure of the maximal components in the critical regime of both the configuration model and the uniform simple random graph model with prescribed degree sequence under finite third moment assumption on the degree sequence. As a substantive application we answer a question raised by Černý and Teixeira study by obtaining the metric space scaling limit of maximal components in the vacant set left by random walks on random regular graphs. [ABSTRACT FROM AUTHOR]

Recently, Grynkiewicz et al. (2013), using tools from additive combinatorics and group theory, proved necessary and sufficient conditions under which the linear congruence a 1 x 1 + ⋯ + a k x k ≡ b (mod n) , where a 1 , ... , a k , b , n (n ≥ 1) are arbitrary integers, has a solution 〈 x 1 , ... , x k 〉 ∈ Z n k with all x i distinct. So, it would be an interesting problem to give an explicit formula for the number of such solutions. Quite surprisingly, this problem was first considered, in a special case, by Schönemann almost two centuries ago(!) but his result seems to have been forgotten. Schönemann (1839), proved an explicit formula for the number of such solutions when b = 0 , n = p a prime, and ∑ i = 1 k a i ≡ 0 (mod p) but ∑ i ∈ I a i ⁄ ≡ 0 (mod p) for all 0̸ ≠ I ⊊︀ { 1 , ... , k }. In this paper, we generalize Schönemann's theorem using a result on the number of solutions of linear congruences due to D. N. Lehmer and also a result on graph enumeration. This seems to be a rather uncommon method in the area; besides, our proof technique or its modifications may be useful for dealing with other cases of this problem (or even the general case) or other relevant problems. [ABSTRACT FROM AUTHOR]

We study the number of connected graphs with n vertices that cannot be written as the cartesian product of two graphs with fewer vertices. We give an upper bound which implies that for large n almost all graphs are both connected and cartesian primes. For graphs with an even number of vertices, a full asymptotic expansion is obtained. Our method, inspired by Knopfmacher's theory of arithmetical semigroups, is based on reduction to Wright's asymptotic expansion for the number of connected graphs with n vertices. [ABSTRACT FROM AUTHOR]

• Dual graph enumeration algorithm that retains all non-isomorphic dual graphs. • Dual graph partitioning algorithm that identifies all possible RNA subgraphs. • A comprehensive dual graph library and fragment database for RNAs with pseudoknots. Exploring novel RNA topologies is imperative for understanding RNA structure and pursuing its design. Our RNA-As-Graphs (RAG) approach exploits graph theory tools and uses coarse-grained tree and dual graphs to represent RNA helices and loops by vertices and edges. Only dual graphs represent pseudoknotted RNAs fully. Here we develop a dual graph enumeration algorithm to generate an expanded library of dual graph topologies for 2–9 vertices, and extend our dual graph partitioning algorithm to identify all possible RNA subgraphs. Our enumeration algorithm connects smaller-vertex graphs, using all possible edge combinations, to build larger-vertex graphs and retain all non-isomorphic graph topologies, thereby more than doubling the size of our prior library to a total of 110,667 dual graph topologies. We apply our dual graph partitioning algorithm, which keeps pseudoknots and junctions intact, to all existing RNA structures to identify all possible substructures up to 9 vertices. In addition, our expanded dual graph library assigns graph topologies to all RNA graphs and subgraphs, rectifying prior inconsistencies. We update our RAG-3Dual database of RNA atomic fragments with all newly identified substructures and their graph IDs, increasing its size by more than 50 times. The enlarged dual graph library and RAG-3Dual database provide a comprehensive repertoire of graph topologies and atomic fragments to study yet undiscovered RNA molecules and design RNA sequences with novel topologies, including a variety of pseudoknotted RNAs. [ABSTRACT FROM AUTHOR]

This paper solves a problem that was stated by M. A. Harrison in 1973. The problemhas remained open since then, and it is concernedwith counting equivalence classes of n × r binary matrices under row and column permutations. Let I and O denote two sets of vertices, where I ☑ O = Æ, ∣I∣ = n, ∣O∣ = r, and Bu(n, r) denote the set of unlabeled graphs whose edges connect vertices in I and O. Harrison established that the number of equivalence classes of n×r binary matrices is equal to the number of unlabeled graphs in Bu(n, r). He also computed the number of such matrices (hence such graphs) for small values of n and r without providing an asymptotic formula for ∣Bu(n, r)∣. Here, such an asymptotic formula is provided by proving the following two-sided inequality using Polya's Counting Theorem. [ABSTRACT FROM AUTHOR]

Frequent graph pattern mining is one of the most interesting areas in data mining, and many researchers have developed a variety of approaches by suggesting efficient, useful mining techniques by integration of fundamental graph mining with other advanced mining works. However, previous graph mining approaches have faced fatal problems that cannot consider important characteristics in the real world because they cannot process both (1) different element importance and (2) multiple minimum support thresholds suitable for each graph element. In other words, graph elements in the real world have not only frequency factors but also their own importance; in addition, various elements composing graphs may require different thresholds according to their characteristics. However, traditional ones do not consider such features. To overcome these issues, we propose a new frequent graph pattern mining method, which can deal with both different element importance and multiple minimum support thresholds. Through the devised algorithm, we can obtain more meaningful graph pattern results with higher importance. We also demonstrate that the proposed algorithm has more outstanding performance compared to previous state-of-the-art approaches in terms of graph pattern generation, runtime, and memory usage.

Random graph null models have found widespread application in diverse research communities analyzing network datasets, including social, information, and economic networks, as well as food webs, protein-protein interactions, and neuronal networks. The most popular random graph null models, called configuration models, are defined as uniform distributions over a space of graphs with a fixed degree sequence. Commonly, properties of an empirical network are compared to properties of an ensemble of graphs from a configuration model in order to quantify whether empirical network properties are meaningful or whether they are instead a common consequence of the particular degree sequence. In this work we study the subtle but important decisions underlying the specification of a configuration model, and we investigate the role these choices play in graph sampling procedures and a suite of applications. We place particular emphasis on the importance of specifying the appropriate graph labeling---stub-labeled or vertex-labeled---under which to consider a null model, a choice that closely connects the study of random graphs to the study of random contingency tables. We show that the choice of graph labeling is inconsequential for studies of simple graphs, but can have a significant impact on analyses of multigraphs or graphs with self-loops. The importance of these choices is demonstrated through a series of three in-depth vignettes, analyzing three different network datasets under many different configuration models and observing substantial differences in study conclusions under different models. We argue that in each case, only one of the possible configuration models is appropriate. While our work focuses on undirected static networks, it aims to guide the study of directed networks, dynamic networks, and all other network contexts that are suitably studied through the lens of random graph null models. [ABSTRACT FROM AUTHOR]

In their seminal work, Erdős and Rényi [3] uncovered a sharp transition in the size of the largest connected component of random graphs. Here, we consider feedforward networks which have important applications in artificial intelligence and sensory neural networks [9] [13] . We obtain generating functions for both the total number of feedforward networks and the number of connected feedforward networks as well as an asymptotic expression for the total number of feedforward networks. Moreover, considering a random family of feedforward networks, we uncover a sharp threshold in their probability of being connected. [ABSTRACT FROM AUTHOR]

In this extended abstract, we present the first combinatorial scheme for counting labeled 4-regular planar graphs through a complete recursive decomposition. More precisely, we show that the exponential generating function counting labeled 4-regular planar graphs can be computed effectively as the solution of a system of equations. From here we can extract the coefficients by means of algebraic calculus. As a by-product, we can also compute the algebraic generating function counting labeled 3-connected 4-regular planar maps. [ABSTRACT FROM AUTHOR]

We consider packings of congruent circles on a square flat torus, i.e., periodic (w.r.t. a square lattice) planar circle packings, with the maximal circle radius. This problem is interesting due to a practical reason-the problem of 'super resolution of images.' We have found optimal arrangements for $$N=6$$ , 7 and 8 circles. Surprisingly, for the case $$N=7$$ there are three different optimal arrangements. Our proof is based on a computer enumeration of toroidal irreducible contact graphs. [ABSTRACT FROM AUTHOR]

A novel algorithm has been proposed to find all possible simple paths between any two given nodes of a graph which is a NP-hard problem. First a novel approach to represent a graph using Boolean operators has been structured. The unique Boolean expression is used to find all possible paths between any two nodes. The analysis of Boolean expression based representation of a graph reveals that the problem is in NPhard. Further a necessary and sufficient condition is given to show that the problem is not NP-complete. A detail theoretical analysis and experimental results has been given in support of its ingenuity. [ABSTRACT FROM AUTHOR]

Let $\Gamma$ be a quiver on $n$ vertices $v_1, v_2, \ldots , v_n$ with $g_{ij}$ edges between $v_i$ and $v_j$, and let $\boldsymbol{\alpha} \in \mathbb{N}^n$. Hua gave a formula for $A_{\Gamma}(\boldsymbol{\alpha}, q)$, the number of isomorphism classes of absolutely indecomposable representations of $\Gamma$ over the finite field $\mathbb{F}_q$ with dimension vector $\boldsymbol{\alpha}$. We use Hua's formula to show that the derivatives of $A_{\Gamma}(\boldsymbol{\alpha}, q)$ with respect to $q$, when evaluated at $q = 1$, are polynomials in the variables $g_{ij}$, and we can compute the highest degree terms in these polynomials. The formulas for these coefficients depend on the enumeration of certain families of connected graphs. This note simply gives an overview of these results; a complete account of this research is available on the arXiv and has been submitted for publication.

Abstract: The stationary birth-only, or Yule–Furry, process for rooted binary trees has been analysed with a view to developing explicit expressions for two fundamental statistical distributions: the probability that a randomly selected leaf is preceded by N nodes, or “ancestors”, and the probability that two randomly selected leaves are separated by N nodes. For continuous-time Yule processes, the first of these distributions is presented in closed analytical form as a function of time, with time being measured with respect to the moment of “birth” of the common ancestor (which is essentially inaccessible to phylogenetic analysis), or with respect to the instant at which the first bifurcation occurred. The second distribution is shown to follow in an iterative manner from a hierarchy of second-order ordinary differential equations. For Yule trees of a given number n of tips, expressions have been derived for the mean and variance for each of these distributions as functions of n, as well as for the distributions themselves. In addition, it is shown how the methods developed to obtain these distributions can be employed to find, with minor effort, expressions for the expectation values of two statistics on Yule trees, the Sackin index (sum over all root-to-leaf distances), and the sum over all leaf-to-leaf distances. [Copyright &y& Elsevier]

Abstract: A minor-closed class of graphs is a set of labelled graphs which is closed under isomorphism and under taking minors. For a minor-closed class , let be the number of graphs in which have n vertices. The growth constant of is . We study the properties of the set Γ of growth constants of minor-closed classes of graphs. Among other results, we show that Γ does not contain any number in the interval , besides 0, 1, ξ and 2, where . An infinity of further gaps is found by determining all the possible growth constants between 2 and . Our results give in fact a complete characterization of all the minor-closed classes with growth constant at most δ in terms of their excluded minors. [Copyright &y& Elsevier]

Abstract: Let Γ be a quiver on n vertices with edges between and , and let . Hua gave a formula for , the number of isomorphism classes of absolutely indecomposable representations of Γ over the finite field with dimension vector α . Kac showed that is a polynomial in q with integer coefficients. Using Hua''s formula, we show that for each integer , the sth derivative of with respect to q, when evaluated at , is a polynomial in the variables , and we compute the highest degree terms in this polynomial. Our formulas for these coefficients depend on the enumeration of certain families of connected graphs. [Copyright &y& Elsevier]

Abstract: For every , we define as the class of graphs with tree-depth at most k, i.e. the class containing every graph G admitting a valid colouring such that every -path between two vertices where contains a vertex z where . In this paper we study the class of minor-minimal elements not belonging in for every . We give a precise characterization of and prove a structural lemma for creating graphs , . As a consequence, we obtain a precise characterization of all acyclic graphs in and we prove that they are exactly . [Copyright &y& Elsevier]

Abstract: For , let be the class containing every graph that contains k vertices meeting all its cycles. The minor-obstruction set for is the set containing all minor-minimal graph that does not belong to . We denote by the set of all outerplanar graphs in . In this paper, we provide a precise characterization of the class . Then, using the symbolic method, we prove that where and . [Copyright &y& Elsevier]