Springer Science and Business Media LLC
Công bố khoa học tiêu biểu
* Dữ liệu chỉ mang tính chất tham khảo
Sắp xếp:
The Effect of Local Majority on Global Majorityin Connected Graphs
Springer Science and Business Media LLC - Tập 34 - Trang 1469-1487 - 2018
Let $$\mathcal G$$ be an infinite family of connected graphs and let k be a
positive integer. We say that k is forcing for $$\mathcal G$$ if for all $$G \in
\mathcal G$$ but finitely many, the following holds. Any $$\{-1,1\}$$ -weighing
of the edges of G for which all connected subgraphs on k edges are positively
weighted implies that G is positively weighted. Otherwise, we say that it is
weakly f...
Graph Bases and Diagram Commutativity
Springer Science and Business Media LLC - Tập 34 - Trang 523-534 - 2018
Given two cycles A and B in a graph, such that $$A\cap B$$ is a non-trivial
path, the connected sum $$A\hat{+} B$$ is the cycle whose edges are the
symmetric difference of E(A) and E(B). A special kind of cycle basis for a
graph, a connected sum basis, is defined. Such a basis has the property that a
hierarchical method, building successive cycles through connected sum,
eventually reaches all the ...
Snarks, Hypohamiltonian Graphs and Non-Supereulerian Graphs
Springer Science and Business Media LLC - Tập 32 - Trang 2267-2273 - 2016
A graph G is hypohamiltonian if it is not Hamiltonian but for each $$v\in V(G)$$
, the graph $$G-v$$ is Hamiltonian. A graph is supereulerian if it has a
spanning Eulerian subgraph. A graph G is called collapsible if for every even
subset $$R\subseteq V(G)$$ , there is a spanning connected subgraph H of G such
that R is the set of vertices of odd degree in H. A graph is reduced if it has
no nontri...
Codings of graphs with binary edge labels
Springer Science and Business Media LLC - Tập 10 - Trang 1-10 - 1994
LetG(V,E) be a graph. A mappingf:E→{0,1} m is called a (binary) coding ofG, if
the induced mapping $$g:V \to \{ 0,1\} ^m ,g(\upsilon ) = \sum\limits_{e
\mathrel\backepsilon v} {f(e)} $$ , assigns different vectors to the vertices.
For the Boolean sum,f is called aB-code, and for the mod 2 sum anM-code. Letm B
(G) resp.m M (G) be the smallest lengthm for whichB-codes resp.M-codes are
possible. Triv...
$$M_{24}$$ -Orbits of Octad Triples
Springer Science and Business Media LLC - Tập 34 - Trang 1429-1443 - 2018
An octad triple is a set of three octads, octads being the blocks of the
S(5, 8, 24) Steiner system. In this paper we determine the orbits of $$M_{24}$$
, the largest Mathieu group, upon the set of octad triples.
Tight Bounds for Illuminating and Covering of Orthotrees with Vertex Lights and Vertex Beacons
Springer Science and Business Media LLC - Tập 36 - Trang 617-630 - 2020
We consider two variants of the Art Gallery Problem: illuminating orthotrees
with a minimum set of vertex lights, and covering orthotrees with a minimum set
of vertex beacons. An orthotree P is a simply connected orthogonal polyhedron
that is the union of a set S of cuboids glued face to face such that the graph
whose vertices are the cuboids of S, two of which are adjacent if they share a
common ...
Small Edge Sets Meeting all Triangles of a Graph
Springer Science and Business Media LLC - Tập 28 - Trang 381-392 - 2011
It was conjectured in 1981 by the third author that if a graph G does not
contain more than t pairwise edge-disjoint triangles, then there exists a set of
at most 2t edges that shares an edge with each triangle of G. In this paper, we
prove this conjecture for odd-wheel-free graphs and for ‘triangle-3-colorable’
graphs, where the latter property means that the edges of the graph can be
colored wit...
Chromatically Supremal Decompositions of Graphs
Springer Science and Business Media LLC - Tập 26 - Trang 369-382 - 2010
If G is a graph, a G-decomposition of a host graph H is a partition of the edges
of H into subgraphs of H which are isomorphic to G. The chromatic index of a
G-decomposition of H is the minimum number of colors required to color the parts
of the decomposition so that parts which share a common node get different
colors. We establish an upper bound on the chromatic index and characterize
those deco...
Counting Hamiltonian Cycles on Quartic 4-Vertex-Connected Planar Graphs
Springer Science and Business Media LLC - Tập 36 - Trang 387-400 - 2019
We show that counting Hamiltonian cycles on quartic 4-vertex-connected planar
graphs is $$\#P$$-complete under many-one counting (“weakly parsimonious”)
reductions, and that no Fully Polynomial-time Randomized Approximation Scheme
(FPRAS) can exist for this integer counting problem unless $$NP = RP$$.
A Note on Heterochromatic C 4 in Edge-Colored Triangle-Free Graphs
Springer Science and Business Media LLC - Tập 28 Số 6 - Trang 901-905 - 2012
Tổng số: 1,991
- 1
- 2
- 3
- 4
- 5
- 6
- 10