Search

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 Schonemann almost two centuries ago(!) but his result seems to have been forgotten. Schonemann (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 Schonemann’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.

Combinatorial properties of zeons have been applied to graph enumeration problems, graph colorings, routing problems in communication networks, partition-dependent stochastic integrals, and Boolean satisfiability. Power series of elementary zeon functions are naturally reduced to finite sums by virtue of the nilpotent properties of zeons. Further, the zeon extension of any analytic complex function has zeon polynomial representations on associated equivalence classes of zeons. In this paper, zeros of polynomials over complex zeons are considered. Existing results for real zeon polynomials are extended to the complex case and new results are established. In particular, a fundamental theorem of zeon algebra is established for spectrally simple zeros of complex zeon polynomials, and an algorithm is presented that allows one to find spectrally simple zeros when they exist. As an application, inverses of zeon extensions of analytic functions are computed using polynomial methods.

Explicit expressions for the numbers of labeled geodetic bicyclic, tricyclic, and tetracyclic graphs with a given number of vertices are obtained.

The paper considers boundaries of memory necessary and sufficient for storage of undirected ordered rooted connected graphs, both numbered and unnumbered. The introduction contains the basic definitions and the problem statement. A graph is rooted if one of its vertices is marked as a root. A graph is ordered if for each of its vertices all the incident edges are ordered (numbered). A graph is numbered if all its vertices are numbered with different integer numbers (from 0 to n -1, where n is the number of vertices). Two undirected ordered graphs G and G` are weakly isomorphic if there exists a one-to-one correspondence between their vertices, for which corresponding vertices has the same degrees (numbers of incident edges) and two edges having corresponding ends and the same numbers in these ends, also have the other ends corresponding. Isomorphism of rooted graphs should also correspond their roots. Isomorphism of numbered graphs should also correspond the vertices with the same numbers. Graphs are considered up to weak isomorphism. It is shown that the memory necessary and sufficient for storage of any graph has the size Q( mlogn ) for numbered graphs, Q( n +( m - n +1) logn ) for unnumbered graphs with the number of vertices n and the number of edges m , and Q( n 2 logn ) for graphs without multiple edges and loops with the number of vertices n . It is also shown that the memory sufficient for storage of an edge sequence of length O ( n ) or a spanning tree, has the O ( nlog ( n D)) or O ( nlog D) size, respectively, where D is the maximum vertex degree.

In this chapter, I will talk about some of the enumerative combinatorics problems that have interested researchers during the last decades. For some of those enumeration problems, it is possible to obtain closed mathematical expressions, and for some other it is possible to obtain an estimation by the use of asymptotic methods. Some of the methods used in both cases will be covered in this chapter as well as some application of graph enumeration in different fields. An overview about the enumeration of trees will be given as an example of combinatorial problem solved in a closed mathematical form. Similarly, the problem of enumeration of regular graphs will be discussed as an example of combinatorial enumeration for which it is hard to obtain a closed mathematical form solution and apply the asymptotic estimation method used frequently in analytic combinatorics for this end. An example of application of the enumerative combinatorics for obtaining a result of applicability criteria of selection nodes in a virus spreading control problem will be given as well.

We deduce a new formula for the number of labeled connected graphs with given order and number of edges in terms of the block generating function. Applying this formula, we exactly and asymptotically enumerate cacti with given order and cyclomatic number.

In this paper, mathematical methods of the interaction analysis of protein networks are developed. The main element of this analysis is a construction and enumeration of all shortest ways connecting two separated proteins in the network. The results obtained are illustrated by the Arabidopsis protein network that is of high importance for bioengineering.

An antichain is here regarded as a hypergraph that satisfies the following property: neither of every two different edges is a subset of the other one. The paper is devoted to the enumeration of antichains given on an n-set and having one or more of the following properties: being labeled or unlabeled; being ordered or unordered; being a cover (or a proper cover); and finally, being a T0-, T1- or T2-hypergraph. The problem of enumeration of these classes comprises, in fact, different modifications of Dedekind?s problem. Here a theorem is proved, with the help of which a greater part of these classes can be enumerated. The use of the formula from the theorem is illustrated by enumeration of labeled antichains, labeled T0-antichains, ordered unlabeled antichains, and ordered unlabeled T0-antichains. Also a list of classes that can be enumerated in a similar way is given. Finally, we perform some concrete counting, and give a table of digraphs that we used in the counting process.

In this paper we provide exponential-time algorithms to enumerate the maximal irredundant sets of chordal graphs and two of their subclasses. We show that the maximum number of maximal irredundant sets of a chordal graph is at most \(1.7549^n\), and these can be enumerated in time \(O(1.7549^n)\). For interval graphs, we achieve the better upper bound of \(1.6957^n\) for the number of maximal irredundant sets and we show that they can be enumerated in time \(O(1.6957^n)\). Finally, we show that forests have at most \(1.6181^n\) maximal irredundant sets that can be enumerated in time \(O(1.6181^n)\). We complement the latter result by providing a family of forests having at least \(1.5292^n\) maximal irredundant sets.

The task of listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a significant body of work contributing to both theoretical aspects (e.g., lower and upper bounds on running time, adaption to new computational models) as well as practical aspects (e.g. algorithms tuned for large graphs). Motivated by the fact that the worst-case running time is cubic, we perform a systematic parameterized complexity study of triangle enumeration. We provide both positive results (new enumerative kernelizations, "subcubic" parameterized solving algorithms) as well as negative results (presumable uselessness in terms of "faster" parameterized algorithms of certain parameters such as graph diameter). To this end, we introduce new and extend previous concepts., Appeared at FCT 2017

© . This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ 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.

We propose an output-sensitive algorithm for the enumeration of all maximal bicliques in a bipartite graph, tailored to the case when the degree distribution in one partite set is very skewed. We accomplish a worst-case bound better than previously known general bounds if, e.g., the degree sequence follows a power law. We propose a biclique enumeration algorithm for bipartite graphs.The algorithm is tailored to very non-uniform degree distributions.This case is motivated by automatic multiple-document summarization.

For the problem of enumerating cuts of graphs, Provan and Shier have provided a framework of enumeration that can be applied for the enumeration of various types of cuts such as minimal (s, t)-cuts in an undirected graph, minimal (s, t)-cuts in a directed graph, minimal (s, K)-cuts in an undirected graph, etc. In this paper we generalize their framework and provide an enumerating method that works in a looser condition, providing a possibility of its application easier. We demonstrate its use by giving an algorithm for the enumeration problem that contains the problem of listing minimal (s, K)-cuts in an undirected graph.

Робота присвячена перелiченню розбиттiв деяких класiв мультимножин, $n$-вершинних регулярних графiв другого степеня та бiтрансверсалей $n$-го порядку.

In the paper we report on the parallel enumeration of the degree sequences (their number is denoted by G(n)) and zerofree degree sequences (their number is denoted by (Gz(n)) of simple graphs on n = 30 and n = 31 vertices. Among others we obtained that the number of zerofree degree sequences of graphs on n = 30 vertices is Gz(30) = 5 876 236 938 019 300 and on n = 31 vertices is Gz(31) = 22 974 847 474 172 374. Due to Corollary 21 in [52] these results give the number of degree sequences of simple graphs on 30 and 31 vertices.

A solution to the shortest path enumeration problem can find numerous applications in studying issues related to interconnection networks. In this paper, we enumerate the number of shortest paths between any two vertices in an arrangement graph by establishing a bijection between these shortest paths and a collection of ordered forests of certain bi-colored trees, via minimum factorizations of permutations corresponding to such vertices in terms of so-called arrangement transpositions, and then count the number of these forests with the help of an existing result on the enumeration of such bi-colored trees. Our result generalizes previous ones and can be applied to solve the same problem for other related graphs such as the alternating group graph. On the other hand, the techniques applied to derive such an enumeration result further extend the ongoing work of counting the number of minimum factorizations of a permutation in terms of a certain type of transposition, a rather interesting problem in the area of algebraic combinatorics.

Connected Vertex Cover is one of the classical problems of computer science, already mentioned in the monograph of Garey and Johnson [15]. Although the optimization and decision variants of finding connected vertex covers of minimum size or weight are well studied, surprisingly there is no work on the enumeration or maximum number of minimal connected vertex covers of a graph. In this paper we show that the maximum number of minimal connected vertex covers of a graph is \(O(1.8668^n)\), and these can be enumerated in time \(O(1.8668^n)\). For graphs of chordality at most 5, we are able to give a better upper bound, and for chordal graphs and distance-hereditary graphs we are able to give tight bounds on the maximum number of minimal connected vertex covers.

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 family of 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 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 vignettes, analyzing 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., Comment: To appear in SIAM Review, June 2018. Code available at github.com/joelnish/double-edge-swap-mcmc. v3 fixed minor typos

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: (i) 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 (ii) 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 Cerny and Teixeira by obtaining the metric space scaling limit of maximal components in the vacant set left by random walks on random regular graphs., Comment: 44 pages, 5 figures; to appear in Random Structures & Algorithms

For every k ⩾ 0 , we define G k as the class of graphs with tree-depth at most k, i.e. the class containing every graph G admitting a valid colouring ρ : V ( G ) → { 1 , … , k } such that every ( x , y ) -path between two vertices where ρ ( x ) = ρ ( y ) contains a vertex z where ρ ( z ) > ρ ( x ) . In this paper we study the class obs ( G k ) of minor-minimal elements not belonging in G k for every k ⩾ 0 . We give a precise characterization of G k , k ⩽ 3 and prove a structural lemma for creating graphs G ∈ obs ( G k ) , k > 0 . As a consequence, we obtain a precise characterization of all acyclic graphs in obs ( G k ) and we prove that they are exactly 1 2 2 2 k − 1 − k ( 1 + 2 2 k − 1 − k ) .

We study algorithms for @?SAT and its generalized version @?GENSAT, the problem of computing the number of satisfying assignments of a set of propositional clauses @S. For this purpose we consider the clauses given by their incidence graph, a signed bipartite graph SI(@S), and its derived graphs I(@S) and P(@S). It is well known, that, given a graph of tree-width k, a k-tree decomposition can be found in polynomial time. Very recently Oum and Seymour have shown that, given a graph of clique-width k, a (2^3^k^+^2-1)-parse tree witnessing clique-width can be found in polynomial time. In this paper we present an algorithm for @?GENSAT for formulas of bounded tree-width k which runs in time 4^k(n+n^2.log"2(n)), where n is the size of the input. The main ingredient of the algorithm is a splitting formula for the number of satisfying assignments for a set of clauses @S where the incidence graph I(@S) is a union of two graphs G"1 and G"2 with a shared induced subgraph H of size at most k. We also present analogue improvements for algorithms for formulas of bounded clique-width which are given together with their derivation. This considerably improves results for @?SAT, and hence also for SAT, previously obtained by Courcelle et al. [On the fixed parameter complexity of graph enumeration problems definable in monadic second order logic, Discrete Appl. Math. 108 (1-2) (2001) 23-52].

We describe a general construction principle for a class of self-similar graphs. For various enumeration problems, we show that this construction leads to polynomial systems of recurrences and provide methods to solve these recurrences asymptotically. This is shown for different examples involving classical self-similar graphs such as the Sierpiński graphs. The enumeration problems we investigate include counting independent subsets, matchings and connected subsets.

METHODS Algebraic and Geometric Methods in Enumerative Combinatorics Introduction What is a Good Answer? Generating Functions Linear Algebra Methods Posets Polytopes Hyperplane Arrangements Matroids Acknowledgments Analytic Methods Helmut Prodinger Introduction Combinatorial Constructions and Associated Ordinary Generating Functions Combinatorial Constructions and Associated Exponential Generating Functions Partitions and Q-Series Some Applications of the Adding a Slice Technique Lagrange Inversion Formula Lattice Path Enumeration: The Continued Fraction Theorem Lattice Path Enumeration: The Kernel Method Gamma and Zeta Function Harmonic Numbers and Their Generating Functions Approximation of Binomial Coefficients Mellin Transform and Asymptotics of Harmonic Sums The Mellin-Perron Formula Mellin-Perron Formula: Divide-and-Conquer Recursions Rice's Method Approximate Counting Singularity Analysis of Generating Functions Longest Runs in Words Inversions in Permutations and Pumping Moments Tree Function The Saddle Point Method Hwang's Quasi-Power Theorem TOPICS Asymptotic Normality in Enumeration E. Rodney Canfield The Normal Distribution Method 1: Direct Approach Method 2: Negative Roots Method 3: Moments Method 4: Singularity Analysis Local Limit Theorems Multivariate Asymptotic Normality Normality in Service to Approximate Enumeration Trees Michael Drmota Introduction Basic Notions Generating Functions Unlabeled Trees Labeled Trees Selected Topics on Trees Planar maps Gilles Schaeffer What is a Map? Counting Tree-Rooted Maps Counting Planar Maps Beyond Planar Maps, an Even Shorter Account Graph Enumeration Marc Noy Introduction Graph Decompositions Connected Graphs with Given Excess Regular Graphs Monotone and Hereditary Classes Planar Graphs Graphs on Surfaces and Graph Minors Digraphs Unlabelled Graphs Unimodality, Log-Concavity, Real-Rootedness and Beyond Petter Branden Introduction Probabilistic Consequences of Real-Rootedness Unimodality and G-Nonnegativity Log-Concavity and Matroids Infinite Log-Concavity The Neggers-Stanley Conjecture Preserving Real-Rootedness Common Interleavers Multivariate Techniques Historical Notes Words Dominique Perrin and Antonio Restivo Introduction Preliminaries Conjugacy Lyndon words Eulerian Graphs and De Bruijn Cycles Unavoidable Sets The Burrows-Wheeler Transform The Gessel-Reutenauer Bijection Suffix Arrays Tilings James Propp Introduction and Overview The Transfer Matrix Method Other Determinant Methods Representation-Theoretic Methods Other Combinatorial Methods Related Topics, and an Attempt at History Some Emergent Themes Software Frontiers Lattice Path Enumeration Christian Krattenthaler Introduction Lattice Paths Without Restrictions Linear Boundaries of Slope 1 Simple Paths with Linear Boundaries of Rational Slope, I Simple Paths with Linear Boundaries with Rational Slope, II Simple Paths with a Piecewise Linear Boundary Simple Paths with General Boundaries Elementary Results on Motzkin and Schroder Paths A continued Fraction for the Weighted Counting of Motzkin Paths Lattice Paths and Orthogonal Polynomials Motzkin Paths in a Strip Further Results for Lattice Paths in the Plane Non-Intersecting Lattice Paths Lattice Paths and Their Turns Multidimensional Lattice Paths Multidimensional Lattice Paths Bounded by a Hyperplane Multidimensional Paths With a General Boundary The Reflection Principle in Full Generality Q-Counting Of Lattice Paths and Rogers-Ramanujan Identities Self-Avoiding Walks Catalan Paths and q t-enumeration James Haglund Introduction to q-Analogues and Catalan Numbers The q t-Catalan Numbers Parking Functions and the Hilbert Series The q t-Schroder Polynomial Rational Catalan Combinatorics Permutation Classes Vincent Vatter Introduction Growth Rates of Principal Classes Notions of Structure The Set of All Growth Rates Parking Functions Catherine H. Yan Introduction Parking Functions and Labeled Trees Many Faces of Parking Functions Generalized Parking Functions Parking Functions Associated with Graphs Final Remarks Standard Young Tableaux Ron Adin and Yuval Roichman Introduction Preliminaries Formulas for Thin Shapes Jeu de taquin and the RS Correspondence Formulas for Classical Shapes More Proofs of the Hook Length Formula Formulas for Skew Strips Truncated and Other Non-Classical Shapes Rim Hook and Domino Tableaux q-Enumeration Counting Reduced Words Appendix 1: Representation Theoretic Aspects Appendix 2: Asymptotics and Probabilistic Aspects Computer Algebra Manuel Kauers Introduction Computer Algebra Essentials Counting Algorithms Symbolic Summation The Guess-and-Prove Paradigm Index

We characterize the toroidal graphs with no K3,3-subdivisions as canonical compositions in which 2-pole planar networks are substituted for the edges of non-planar cores. This structure enables us to enumerate these graphs. We describe an explicit enumerative approach that requires unlabelled enumeration of 2-connected planar graphs.

We study parameterized enumeration problems where we are interested in all solutions of limited size rather than just some solution of minimum cardinality. (Actually, we have to enumerate the inclusion-minimal solutions in order to get fixed-parameter tractable (FPT) results.) Two novel concepts are the notion of a full kernel that contains all small solutions and implicit enumeration of solutions in form of compressed descriptions. In particular, we study combinatorial and computational bounds for the transversal hypergraph (vertex covers in graphs is a special case), restricted to hyperedges with at most k elements. As an example, we apply the results and further special-purpose techniques to almost-perfect phylogeny reconstruction, a problem in computational biology.

Acyclic hypergraphs are analogues of forests in graphs. They are very useful in the design of databases. In this article, the maximum size of an acyclic hypergraph is determined and the number of maximum r-uniform acyclic hypergraphs of order n is shown to be $$ {\left( {\begin{array}{*{20}c} {n} \\ {{r - 1}} \\ \end{array} } \right)}{\left( {n{\left( {r - 1} \right)} - r^{2} + 2r} \right)}^{{n - r - 1}} . $$

IEEE Transactions on Computers, Vol. 50, No. 9, September 2001 This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted. ÐIn an irredundant sum-of-products expression (ISOP), each product is a prime implicant (PI) and no product can be deleted without changing the function. Among the ISOPs for some function f, a worst ISOP (WSOP) is an ISOP with the largest number of PIs and a minimum ISOP (MSOP) is one with the smallest number. We show a class of functions for which the Minato-Morreale ISOP algorithm produces WSOPs. Since the ratio of the size of the WSOP to the size of the MSOP is arbitrarily large when n, the number of variables, is unbounded, the Minato-Morreale algorithm can produce results that are very far from minimum. We present a class of multiple-output functions whose WSOP size is also much larger than its MSOP size. For a set of benchmark functions, we show the distribution of ISOPs to the number of PIs. Among this set are functions where the MSOPs have almost as many PIs as do the WSOPs. These functions are known to be easy to minimize. Also, there are benchmark functions where the fraction of ISOPs that are MSOPs is small and MSOPs have many fewer PIs than the WSOPs. Such functions are known to be hard to minimize. For one class of functions, we show that the fraction of ISOPs that are MSOPs approaches 0 as n approaches infinity, suggesting that such functions are hard to minimize.

The sextet polynomial that counts different ways of selecting varying number of resonating sextets on the hexagonal system is computed using a search based symbol manipulation algorithm. This is a #P Complete combinatorial enumeration problem, and artificial intelligence (AI) is employed for efficient enumeration. This is done by selective exploration of the semantic tree defined for that purpose. Hexagons of the graph are defined as symbols and each node of the tree is defined as a set of mutually disjoint hexagon patterns of the graph. The sextet polynomial is generated by enumerating a suitable subset of the nodes of the tree. A pruning heuristic that avoids redundant branches by a priori learning at selected intelligent branches of the semantic tree is designed.

In this paper we give an enumeration formula of the outerplanar graphs by means of graph compression, group theory and combinatorial numbers. Some simple examples are exhibited for illustrating the method. The computational results are shown in the table at the end of this paper.

This paper gives an ordinary generating function for unlabelled bicolored graphs with a given number of odd vertices, where the cardinalities of the bipartite sets are equal. Moreover, the generating functions for the cardinality of each bipartite set from 1 to 8 are listed.

We give a recursion formula to generate all the equivalence classes of connected graphs with coefficients given by the inverses of the orders of their groups of automorphisms. We use an algebraic graph representation to apply the result to the enumeration of connected graphs, all of whose biconnected components have the same number of vertices and edges. The proof uses Abel’s binomial theorem and generalizes Dziobek’s induction proof of Cayley’s formula.

We reduce (in polynomial time) the enumeration of minimal dominating sets in interval and permutation graphs to the enumeration of paths in directed acyclic graphs(DAGs). As a consequence, we can enumerate with linear delay, after a polynomial time pre-processing, minimal dominating sets in interval and permutation graphs. We can also count them in polynomial time. This improves considerably upon previously known results on interval graphs, and up to our knowledge no output polynomial time algorithm for the enumeration of minimal dominating sets and their counting were known for permutation graphs.

Edge coloring, total coloring and L(2,1)-labeling are well-studied NP-hard graph problems. Even the versions asking whether a graph has a coloring with few colors or a labeling with few labels remain NP-hard on graphs of small maximum degree. This paper studies enumeration and counting problems on edge colorings, total colorings and L(2,1)-labelings of graphs. One part deals with the enumeration of all edge 3-colorings, all total 4-colorings and all L(2,1)-labelings of span 5 of a given connected cubic graph. Branching algorithms to solve these enumeration problems are established. They imply upper bounds on the maximum number of edge 3-colorings, total 4-colorings and L(2,1)-labelings of span 5 in any n-vertex connected cubic graphs. Corresponding combinatorial lower bounds are also provided. The other part of the paper studies dynamic programming algorithms solving counting problems. On one hand, algorithms to count the number of edge k-colorings and total k-colorings for graphs of bounded pathwidth are given. On the other hand, an algorithm to count the number of L(2,1)-labelings of span 4 for graphs of maximum degree three are given.

The main theme of this article is that counting orbits of an infinite permutation group on finite subsets or tuples is very closely related to combinatorial enumeration; this point of view ties together various disparate ``stories''. Among these are reconstruction problems, the relation between connected and arbitrary graphs, the enumeration of N-free posets, and some of the combinatorics of Stirling numbers.

A computer program with O(p.n) time complexity is developed for the combinatorial enumeration of peak to valley augmenting paths of any n-vertex benzenoid graph with p number of peaks, using sets as its primary data structure. Peaks and valleys are recognized by using a breadth-first labeling procedure. The code computes the P-V matrix whose determinant is the number of Kekule structures of the given graph G. this program can handle very large graphs and takes only a few seconds to compute the P-V matrix of the typical graph even on a personal computer. As the code is very efficient and compact it can be used in any program that calculates the Kekule structure count (KSC) as an intermediate result.

International audience; We study enumeration problems using probabilistic methods, with application to verification problems. We consider the enumeration of monomials of a polynomial given as a black box, and the enumeration of discrete points which separate two polytopes in a space of dimension n, using a random walk which provides witnesses if the volume of the difference of the polytopes is large enough. The first method allows to enumerate all words of a given size which distinguish two probabilistic automata with a polynomial delay. The second method enumerates words which ε-distinguish two nondeterministic finite automata.We also enumerate strategies which ε-distinguish two Markov Decision Processes in time polynomial in the dimension of their statistical representation.

We prove that line graphs and path graphs have bounded neighbourhood Helly. As a consequence, we obtain output-polynomial time algorithms for enumerating the set of minimal dominating sets of line graphs and path graphs. Therefore, there exists an output-polynomial time algorithm that enumerates the set of minimal edge-dominating sets of any graph.

What Is Enumeration?.- Generating Functions Count.- Working with Generating Functions.- Permutation Groups.- Matrices, Sequences and Sums.- Group Actions and Counting.- Exponential Generating Functions.- Graphs.- partitions and Paths.

Due to a recent revision of Hales's proof of the Kepler Conjecture, the existing verification of the central graph enumeration procedure had to be revised because it now has to cope with more than 109 graphs. This resulted in a new and modular design. This paper primarily describes the reusable components of the new design: a while combinator for partial functions, a theory of worklist algorithms, a stepwise implementation of a data type of sets over a quasi-order with the help of tries, and a plane graph isomorphism checker. The verification turned out not to be in vain as it uncovered a bug in Hales's graph enumeration code.

In this paper, we are interested in the enumeration of minimal dominating sets in graphs. A polynomial delay algorithm with polynomial space in split graphs is presented. We then introduce a notion of maximal extension (a set of edges added to the graph) that keeps invariant the set of minimal dominating sets, and show that graphs with extensions as split graphs are exactly the ones having chordal graphs as extensions. We finish by relating the enumeration of some variants of dominating sets to the enumeration of minimal transversals in hypergraphs.

Enumerative mathematics (also commonly called combinatorics) is concerned with arrangements of a given set of objects according to precise rules. The aim is to count the number of possible arrangements by recognizing and exploiting the patterns that make them up. Sometimes the result is an explicit formula for the count; sometimes different patterns of the same arrangement will result in different expressions which are thus equal. As we shall see, many different branches of mathematics provide strikingly different ways in which we can count. This book explores some of these.

Acyclic walk of a graph is the closed walk whose projection is an acyclic graph. It is shown that the set of acyclic walks of the given graph G coincides with the set of closed walks of all spanning trees of G. Thus, an enumeration of acyclic walks can be performed by enumeration of closed walks of spanning trees and their subgraphs. By using the inclusion—exclusion principle another formula for the number of acyclic walks is derived, in terms of numbers of closed walks of connected subgraphs S of G and in terms of neighbors in S of vertices in G—S.

An efficient method for constructive enumeration of graphs is suggested. The method is based on the so called semicanonical numbering of graphs, that is a numbering much more restrictive than the cooperative numbering. Graph-theoretical properties of the semicanonical numbering make it possible to formulate an exhaustive and nonredundant constructive enumeration of graphs. The approach allows an easy introduction of specifications for molecular graphs.