Results 21 to 30 of about 272 (58)
Sharp Upper Bounds on the Clar Number of Fullerene Graphs
Discussiones Mathematicae Graph Theory, 2018 The Clar number of a fullerene graph with n vertices is bounded above by ⌊n/6⌋ − 2 and this bound has been improved to ⌊n/6⌋ − 3 when n is congruent to 2 modulo 6.
Gao Yang, Zhang Heping
doaj +1 more source
Path separation by short cycles
, 2016 Two Hamilton paths in $K_n$ are separated by a cycle of length $k$ if their union contains such a cycle. For small fixed values of $k$ we bound the asymptotics of the maximum cardinality of a family of Hamilton paths in $K_n$ such that any pair of paths ...
Cibulka +9 more
core +1 more source
, 2015 We show that every 3-regular circle graph has at least two pairs of twin vertices; consequently no such graph is prime with respect to the split decomposition.
Traldi, Lorenzo
core +4 more sources
Voting for Committees in Agreeable Societies
, 2014 We examine the following voting situation. A committee of $k$ people is to be formed from a pool of n candidates. The voters selecting the committee will submit a list of $j$ candidates that they would prefer to be on the committee.
Davis, Matt +2 more
core +1 more source
The classification of partially symmetric 3-braid links
Open Mathematics, 2015 We classify 3-braid links which are amphicheiral as unoriented links, including a new proof of Birman- Menasco’s result for the (orientedly) amphicheiral 3-braid links. Then we classify the partially invertible 3-braid links.
Stoimenov Alexander
doaj +1 more source
Graph connectivity and universal rigidity of bar frameworks [PDF]
, 2014 Let $G$ be a graph on $n$ nodes. In this note, we prove that if $G$ is $(r+1)$-vertex connected, $1 \leq r \leq n-2$, then there exists a configuration $p$ in general position in $R^r$ such that the bar framework $(G,p)$ is universally rigid.
Alfakih, A. Y.
core
Archimedean tiling graphs with Gallai’s property
Analele Stiintifice ale Universitatii Ovidius Constanta: Seria Matematica, 2017 Gallai in 1966 raised the question about the existence of graphs with the property that every vertex is missed by some longest path. This property will be called Gallai’s property.
Chang Zhikui, Yuan Liping
doaj +1 more source
Induced Subgraphs of Johnson Graphs
, 2012 The Johnson graph J(n,N) is defined as the graph whose vertices are the n-subsets of the set {1,2,...,N}, where two vertices are adjacent if they share exactly n - 1 elements.
Benadé +6 more
core +1 more source
Improved bounds for the crossing numbers of K_m,n and K_n
, 2004 It has been long--conjectured that the crossing number cr(K_m,n) of the complete bipartite graph K_m,n equals the Zarankiewicz Number Z(m,n):= floor((m-1)/2) floor(m/2) floor((n-1)/2) floor(n/2). Another long--standing conjecture states that the crossing
de Klerk, E. +4 more
core +2 more sources
A polynomial algorithm for the k-cluster problem on interval graphs
, 2008 This paper deals with the problem of finding, for a given graph and a given natural number k, a subgraph of k nodes with a maximum number of edges. This problem is known as the k-cluster problem and it is NP-hard on general graphs as well as on chordal ...
Mertzios, George B.
core +1 more source