搜索结果: 31-45 共查到“组合数学 graphs”相关记录47条 . 查询时间(0.056 秒)
On the metric dimension of line graphs
Metric dimension resolving set line graph de Brujin digraph Kautz digraph
2011/9/16
Abstract: Let $G$ be a (di)graph. A set $W$ of vertices in $G$ is a \emph{resolving set} of $G$ if every vertex $u$ of $G$ is uniquely determined by its vector of distances to all the vertices in $W$....
Scott's induced subdivision conjecture for maximal triangle-free graphs
Scott's subdivision conjecture maximal triangle-free graphs Combinatorics
2011/9/14
Abstract: Scott conjectured that the class of graphs with no induced subdivision of a given graph is $\chi$-bounded. We verify his conjecture for maximal triangle-free graphs.
Classification of nonorientable regular embeddings of Hamming graphs
Graph embeddings regular embeddings regular map Hamming graphs
2011/9/9
Abstract: By a regular embedding of a graph K in a surface we mean a 2-cell embedding of K in a compact connected surface such that the automorphism group acts regularly on flags. In this paper, we cl...
Arrow ribbon graphs
Graphs on surfaces ribbon graphs Bollobas-Riordan polynomial Tutte polynomial duality virtual links arrow polynomial
2011/9/13
Abstract: We introduce an additional structure on ribbon graphs, arrow structure. We extend the Bollob\'as-Riordan polynomial to ribbon graph with this structure. The extended polynomial satisfies the...
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...
Reverse degree distance of unicyclic graphs
Degree Distance Reverse degree distance Diameter Unicyclic graph Pendant vertices Maximum degree
2011/9/1
Abstract: The reverse degree distance is a connected graph invariant closely related to the degree distance proposed in mathematical chemistry. We determine the unicyclic graphs of given girth, number...
Acyclic and unicyclic graphs whose minimum skew rank is equal to the minimum skew rank of a diametrical path
skew-symmetric matrix minimum skew rank matching diametrical path tree unicyclic graph rank matrix
2011/9/1
Abstract: The minimum skew rank of a simple graph G over the field of real numbers, is the smallest possible rank among all real skew-symmetric matrices whose (i,j)-entry (for i not equal to j) is non...
On augmented eccentric connectivity index of graphs and trees
eccentric connectivity index Combinatorics graphs and trees
2011/9/2
Abstract: In this paper we establish all extremal graphs with respect to augmented eccentric connectivity index among all (simple connected) graphs, among trees and among trees with perfect matching. ...
Classes of graphs with small rank decompositions are chi-bounded
small rank decompositions chi-bounded Combinatorics
2011/9/1
Abstract: A class of graphs G is chi-bounded if the chromatic number of graphs in G is bounded by a function of the clique number. We show that if a class G is chi-bounded,then every class of graphs a...
Abstract: The boxicity of a graph $G=(V,E)$ is the smallest integer $k$ for which there exist $k$ interval graphs $G_i=(V,E_i)$, $1 \le i \le k$, such that $E=E_1 \cap...\cap E_k$. Scheinerman proved ...
Chip-firing games, potential theory on graphs, and spanning trees
Chip-firing games graphs spanning trees Combinatorics
2011/8/26
Abstract: We study the interplay between chip-firing games and potential theory on graphs, characterizing reduced divisors ($G$-parking functions) on graphs as the solution to an energy (or potential)...
Posets of Geometric Graphs
Posets of Geometric Graphs Combinatorics vertex-injective geometric homomorphism
2011/8/26
Abstract: A geometric graph G(bar) is a simple graph drawn in the plane, on points in general position, with straight-line edges. We call G(bar) a geometric realization of the underlying abstract grap...
Abstract: We construct two families of distance-regular graphs, namely the subgraph of the dual polar graph of type B_3(q) induced on the vertices far from a fixed point, and the subgraph of the dual ...
Abstract: In this paper we introduce the nullity of signed graphs, and give some results on the nullity of signed graphs with pendant trees. We characterize the unicyclic signed graphs of order n with...
Optimal Folding of Data Flow Graphs based on Finite Projective Geometry using Lattice Embedding
Projective Geometry Parallel Scheduling Semi-parallel Architecture
2011/9/29
Abstract: A number of computations exist, especially in area of error-control coding and matrix computations, whose underlying data flow graphs are based on finite projective-geometry(PG) based balanc...