搜索结果: 1-14 共查到“组合数学 Graph”相关记录14条 . 查询时间(0.031 秒)
This note deals with the relationship between the total number of $k$-walks in a graph, and the sum of the $k$-th powers of its vertex degrees. In particular, it is shown that the the number of all $k...
We prove that any distributional limit of finite planar graphs in which the degree of the root has an exponential tail is almost surely recurrent. As a corollary, we obtain that the uniform infinite p...
Enumerations of finite topologies associated with a finite graph
Enumerations of finite topologies finite graph Combinatorics
2012/6/19
The number of topologies and non-homeomorphic topologies on a fixed finite set are now known up to $n=18$, $n=16$ but still no complete formula yet (Sloane). There are one to one correspondence among ...
Benjamini--Schramm continuity of root moments of graph polynomials
Graph polynomial of exponential type Tutte polynomial Chromatic polynomial Benjamini–Schramm convergence Sokal bound
2012/4/18
Recently, M.\ Ab\'ert and T.\ Hubai studied the following problem. The chromatic measure of a finite simple graph is defined to be the uniform distribution on its chromatic roots. Ab\'ert and Hubai pr...
For a graph G, its rth power G^r has the same vertex set as G, and has an edge between any two vertices within distance r of each other in G. We give a lower bound for the number of edges in the rth p...
The adjacency matroid of a graph
adjacency delta-matroid interlace polynomial local complement matroid minor Tutte polynomial
2011/9/22
Abstract: If $G$ is a looped graph, then its adjacency matrix represents a binary matroid $M_{A}(G)$ on $V(G)$. $M_{A}(G)$ may be obtained from the delta-matroid represented by the adjacency matrix of...
On a sparse random graph with minimum degree {three}: Likely Posa's sets are large
random sparse graphs degrees longest path Posa sets
2011/9/20
Abstract: We consider the likely size of the endpoint sets produced by Posa rotations, when applied to a longest path in a random graph with $cn,\,c\geq 2.7$ edges that is conditioned to have minimum ...
Normalized graph Laplacians for directed graphs
Normalized graph Laplacians directed graphs Combinatorics
2011/9/20
Abstract: We consider the normalized Laplacian for directed graphs with positive and negative edge weights. We derive basic spectral properties of the normalized Laplacian and identify extremal eigenv...
Bounds for graph regularity and removal lemmas
graph regularity removal lemmas Combinatorics
2011/9/20
Abstract: We show, for any positive integer k, that there exists a graph in which any equitable partition of its vertices into k parts has at least ck^2/\log^* k pairs of parts which are not \epsilon-...
Krausz dimension and its generalizations in special graph classes
Krausz dimension intersection graphs linear k-uniform hypergraphs chordal graphs polar graphs
2011/9/14
Abstract: A {\it krausz $(k,m)$-partition} of a graph $G$ is the partition of $G$ into cliques, such that any vertex belongs to at most $k$ cliques and any two cliques have at most $m$ vertices in com...
Abstract: Graph bootstrap percolation is a deterministic cellular automaton which was introduced by Bollob\'as in 1968, and is defined as follows. Given a graph $H$, and a set $G \subset E(K_n)$ of in...
Some new results in extremal graph theory
extremal graph theory Combinatorics the underpinning ideas
2011/8/26
Abstract: In recent years several classical results in extremal graph theory have been improved in a uniform way and their proofs have been simplified and streamlined. These results include a new Erd\...
Sherali-Adams Relaxations of Graph Isomorphism Polytopes
Sherali-Adams Relaxations Graph Isomorphism Polytopes Combinatorics
2011/8/24
Abstract: We investigate the Sherali-Adams lift & project hierarchy applied to a graph isomorphism polytope whose integer points encode the isomorphisms between two graphs. In particular, the Sherali-...
Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function
Graph Covers Combinatorial Characterization Bethe Entropy Function
2011/1/14
We present a combinatorial characterization of the Bethe entropy function of a factor graph, such a characterization being in contrast to the original, analytical, definition of this
function. We ach...