A Simple Proof of the Perfect Matching Theorem
A simple proof of Whitney's Theorem on connectivity in graphs
In 1932 Whitney showed that a graph with order is 2-connected if and only if any two vertices of are connected by at least two internally-disjoint paths. The above result and its proof have been used in some Graph Theory books, such as in Bondy and Murty’s well-known Graph Theory with Applications. In this note we give a much simple proof of Whitney’s Theorem.
A simple symmetry generating operads related to rooted planar -ary trees and polygonal numbers.
A small trivalent graph of girth 14.
A Sokoban-type game and arc deletion within irregular digraphs of all sizes
Digraphs in which ordered pairs of out- and in-degrees of vertices are mutually distinct are called irregular, see Gargano et al. [3]. Our investigations focus on the problem: what are possible sizes of irregular digraphs (oriented graphs) for a given order n? We show that those sizes in both cases make up integer intervals. The extremal sizes (the endpoints of these intervals) are found in [1,5]. In this paper we construct, with help of Sokoban-type game, n-vertex irregular oriented graphs (irregular...
A solution of Dedekind's problem on the number of isotone Boolean functions.
A solvable case of the set-partitioning problem
A sparse dynamic programming algorithm for alignment with non-overlapping inversions
Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions is still unknown....
A sparse dynamic programming algorithm for alignment with non-overlapping inversions
Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions is...
A Sparse Graph Almost as Good as the Complete Graph on Points in K Dimensions.
A Specht module analog for the rook monoid.
A special class of triangular arrays.
A spectral bound for graph irregularity
The imbalance of an edge in a graph is defined as , where is the vertex degree. The irregularity of is then defined as the sum of imbalances over all edges of . This concept was introduced by Albertson who proved that (where ) and obtained stronger bounds for bipartite and triangle-free graphs. Since then a number of additional bounds were given by various authors. In this paper we prove a new upper bound, which improves a bound found by Zhou and Luo in 2008. Our bound involves the...
A spelling theorem for staggered generalized 2-complexes, with applications.
A Sperner-type theorem for set-partition systems.
A split&push approach to orthogonal drawing.
A stability property for coefficients in Kronecker products of complex characters.
A stationary random graph of no growth rate
We present a random automorphism-invariant subgraph of a Cayley graph such that with probability 1 its exponential growth rate does not exist.
A stochastic complex network model society.
A strengthening of Brooks' Theorem for line graphs.