搜索结果: 1-6 共查到“数学 line graphs”相关记录6条 . 查询时间(0.091 秒)
SANDPILE GROUPS AND SPANNING TREES OF DIRECTED LINE GRAPHS
SANDPILE GROUPS SPANNING TREES DIRECTED LINE GRAPHS
2015/8/14
We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph G and its directed line graph LG. The sandpile group is an abelian group associated to a directed graph, whose...
A connection between the bipartite complements of line graphs and the line graphs with two positive eigenvalues
line graphs graph spectra complements Courant-Weyl inequalities
2012/4/16
In 1974 Cvetkovi\'c and Simi\'c showed which graphs $G$ are the bipartite complements of line graphs. In 2002 Borovi\'canin showed which line graphs $L(H)$ have third largest eigenvalue $\lambda_3\leq...
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$....
Identifying codes in line graphs
Identifying codes Dominating sets Line graphs NP-completeness
2011/8/23
Abstract: An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbours within the code. We study the edge-identify...
A conjecture of Carsten Thomassen states that every 4-connected line graph is hamiltonian. It is known that the conjecture is true for 7-connected line graphs. We improve this by showing that any 5-co...
Boxicity of Line Graphs
Intersection graph Interval graph Boxicity Line graph,Edge graph Hypercube
2010/12/10
Boxicity of a graph H, denoted by box(H), is the mini-mum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in Rk. In this paper.