搜索结果: 1-15 共查到“组合数学 the Number”相关记录15条 . 查询时间(0.046 秒)
On the existence and number of $(k+1)$-kings in $k$-quasi-transitive digraphs
digraph k-king quasi-transitive digraph k-quasi-transitive digraph
2012/6/30
Let $D=(V(D), A(D))$ be a digraph and $k \ge 2$ an integer. We say that $D$ is $k$-quasi-transitive if for every directed path $(v_0, v_1,..., v_k)$ in $D$, then $(v_0, v_k) \in A(D)$ or $(v_k, v_0) \...
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...
Absolutely symmetric trees and complexity of natural number
Absolutely symmetric trees complexity of natural number Combinatorics
2012/5/24
We consider the rooted trees which not have isomorphic representation and introduce a conception of complexity a natural number also. The connection between quantity such trees with $n$ edges and a co...
The p-Domination Number of Complete Multipartite Graphs
p-domination set p-domination number complete multipartite graph
2012/5/9
Let $G=(V,E)$ be a graph and $p$ a positive integer. A subset $S\subseteq V$ is called a $p$-dominating set of $G$ if every vertex not in $S$ has at least $p$ neighbors in $S$. The $p$-domination numb...
Bondage number of grid graphs
Domination bondage number Cartesian product graph strong product graphs direct product graphs
2012/4/18
The bondage number $b(G)$ of a nonempty graph $G$ is the cardinality of a smallest set of edges whose removal from $G$ results in a graph with domination number greater than the domination number of $...
A sharp upper bound for the rainbow 2-connection number of 2-connected graphs
rainbow edge-coloring rainbow k-connection number 2-connected graph ear decomposition
2012/4/18
A path in an edge-colored graph is called {\em rainbow} if no two edges of it are colored the same. For an $\ell$-connected graph $G$ and an integer $k$ with $1\leq k\leq \ell$, the {\em rainbow $k$-c...
Grid Representations and the Chromatic Number
Grid Representations the Chromatic Number Combinatorics
2012/4/17
A grid drawing of a graph maps vertices to grid points and edges to line segments that avoid grid points representing other vertices. We show that there is a number of grid points that some line segme...
The Minimum Number of Dependent Arcs and a Related Parameter of Generalized Mycielski Graphs
acyclic orientation dependent arc source-reversal cover graph generalized Mycielski graph
2012/3/1
Let D be an acyclic orientation of the graph G. An arc of D is dependent if its reversal creates a directed cycle. Let m(G) denote the minimum number of dependent arcs over all acyclic orientations of...
The size of a hypergraph and its matching number
hypergraph its matching number Combinatorics
2011/9/22
Abstract: More than forty years ago, Erd\H{o}s conjectured that for any T <= N/K, every K-uniform hypergraph on N vertices without T disjoint edges has at most max{\binom{KT-1}{K}, \binom{N}{K} - \bin...
Invariant number triangles, eigentriangles and Somos-4 sequences
Invariant number triangles eigentriangles Somos-4 sequences Combinatorics
2011/9/22
Abstract: Using the language of Riordan arrays, we look at two related iterative processes on matrices and determine which matrices are invariant under these processes. In a special case, the invarian...
Counterexamples to a Monotonicity Conjecture for the Threshold Pebbling Number
combinatorics probability theory graph theory graph pebbling pebbling number pebbling threshold
2011/9/20
Abstract: Graph pebbling considers the problem of transforming configurations of discrete pebbles to certain target configurations on the vertices of a graph, using the so-called pebbling move. This p...
The disentangling number for phylogenetic mixtures
disentangling number phylogenetic mixtures Combinatorics
2011/9/8
Abstract: We provide a logarithmic upper bound for the disentangling number on unordered lists of leaf labeled trees. This results is useful for analyzing phylogenetic mixture models. The proof depend...
Large cliques in graphs with high chromatic number
Large cliques high chromatic number graphs Combinatorics
2011/9/5
Abstract: We study graphs whose chromatic number is close to the order of the graph (the number of vertices). Both when the chromatic number is a constant multiple of the order and when the difference...
Chromatic number, clique subdivisions, and the conjectures of Hajos and Erdos-Fajtlowicz
Chromatic number clique subdivisions Hajos and Erdos-Fajtlowicz Combinatorics
2011/9/1
Abstract: For a graph $G$, let $\chi(G)$ denote its chromatic number and $\sigma(G)$ denote the order of the largest clique subdivision in $G$. Let H(n) be the maximum of $\chi(G)/\sigma(G)$ over all ...
About maximal number of edges in hypergraph-clique with chromatic number 3
hypergraph-clique chromatic number 3 Combinatorics
2011/8/31
Abstract: Let $ H = (V,E) $ be a hypergraph. By the chromatic number of a hypergraph $ H = (V,E) $ we mean the minimum number $\chi(H)$ of colors needed to paint all the vertices in $ V $ so that any ...