排序方式: 共有83条查询结果,搜索用时 15 毫秒
71.
Janina Müttel Dieter Rautenbach Friedrich Regen Thomas Sasse 《Graphs and Combinatorics》2013,29(4):1067-1076
We prove lower bounds on the number of different cycle lengths of cubic Hamiltonian graphs that do not contain a fixed subdivision of a claw as an induced subgraph. 相似文献
72.
Albertson [2] has introduced the imbalance of an edge e=uv in a graph G as |dG(u)−dG(v)|. If for a graph G of order n and size m the minimum imbalance of an edge of G equals d, then our main result states that with equality if and only if G is isomorphic to We also prove best-possible upper bounds on the number of edges uv of a graph G such that |dG(u)−dG(v)|≥d for some given d. 相似文献
73.
Piotr Borowiecki Frank Göring Jochen Harant Dieter Rautenbach 《Journal of Graph Theory》2012,71(3):245-259
The well‐known lower bound on the independence number of a graph due to Caro (Technical Report, Tel‐Aviv University, 1979) and Wei (Technical Memorandum, TM 81 ‐ 11217 ‐ 9, Bell Laboratories, 1981) can be established as a performance guarantee of two natural and simple greedy algorithms or of a simple randomized algorithm. We study possible generalizations and improvements of these approaches using vertex weights and discuss conditions on so‐called potential functions pG: V(G)→?0 defined on the vertex set of a graph G for which suitably modified versions of the greedy algorithms applied to G yield independent sets I with . We provide examples of such potentials, which lead to bounds improving the bound due to Caro and Wei. Furthermore, suitably adapting the randomized algorithm we give a short proof of Thiele's lower bound on the independence number of a hypergraph (T. Thiele, J Graph Theory 30 (1999), 213–221). 相似文献
74.
Mitre C. Dourado Van Bang Le Fábio Protti Dieter Rautenbach Jayme L. Szwarcfiter 《Discrete Mathematics》2012,312(22):3357-3363
The class of intersection graphs of unit intervals of the real line whose ends may be open or closed is a strict superclass of the well-known class of unit interval graphs. We pose a conjecture concerning characterizations of such mixed unit interval graphs, verify parts of it in general, and prove it completely for diamond-free graphs. In particular, we characterize diamond-free mixed unit interval graphs by means of an infinite family of forbidden induced subgraphs, and we show that a diamond-free graph is mixed unit interval if and only if it has intersection representations using unit intervals such that all ends of the intervals are integral. 相似文献
75.
Michael Gentner Irene Heinrich Simon Jäger Dieter Rautenbach 《Discrete Mathematics》2018,341(1):119-125
A prominent parameter in the context of network analysis, originally proposed by Watts and Strogatz (1998), is the clustering coefficient of a graph . It is defined as the arithmetic mean of the clustering coefficients of its vertices, where the clustering coefficient of a vertex of is the relative density of its neighborhood if is at least , and otherwise. It is unknown which graphs maximize the clustering coefficient among all connected graphs of given order and size.We determine the maximum clustering coefficients among all connected regular graphs of a given order, as well as among all connected subcubic graphs of a given order. In both cases, we characterize all extremal graphs. Furthermore, we determine the maximum increase of the clustering coefficient caused by adding a single edge. 相似文献
76.
In a pursuit evasion game on a finite, simple, undirected, and connected graph , a first player visits vertices of , where is in the closed neighborhood of for every , and a second player probes arbitrary vertices of , and learns whether or not the distance between and is at most the distance between and . Up to what distance can the second player determine the position of the first? For trees of bounded maximum degree and grids, we show that is bounded by a constant. We conjecture that for every graph of order , and show that if may differ from only if is a multiple of some sufficiently large integer. 相似文献
77.
78.
79.
Rautenbach M Swart P van der Merwe MJ 《Journal of the American Society for Mass Spectrometry》2001,12(5):505-516
The structures and stability of sodiated species of 8-Beta, a linear lipopeptide analog (beta-aminotetradecanoyl-NYNQPNS) of the antifungal peptide iturin A2, were evaluated by electrospray ionization mass spectrometry (ESI-MS). Association of the lipopeptide, 8-Beta, with sodium afforded protection from fragmentation at high cone voltages and increasing collision energy conditions in the ESI-MS. The order of decreasing stability was found as 8-Beta 1Na > 8-Beta 2Na > 8-Beta 3Na > 8-Beta. Substantial differences were found between fragmentation patterns of the free and sodiated molecular species. Breakage of the N-terminal peptide bond of L-Pro generated the major product ions of the free 8-Beta parent ion. Impaired fragmentation of the sodium adducts of 8-Beta, indicated that this bond is protected by sodium complexation. Fragmentation patterns of the sodiated lipopeptide further revealed two specific binding sites for a nonsolvated sodium ion within the two type II beta-turn sequences (beta-aminotetradecanoyl-NYN and QPNS) of the natural iturin A2. It is proposed that specific interaction with sodium takes place with most of the peptide bond oxygens in these turns, and with the Gln sidechain. This interaction leads to stabilized structures in which the peptide backbone, specifically the peptide bonds in which L-Pro participates, is protected against low-energy fragmentation during ESI-MS. 相似文献
80.
For a finite poset P = (V, ≤ ), let _s(P){\cal B}_s(P) consist of all triples (x,y,z) ∈ V
3 such that either x < y < z or z < y < x. Similarly, for every finite, simple, and undirected graph G = (V,E), let Bs(G){\cal B}_s(G) consist of all triples (x,y,z) ∈ V
3 such that y is an internal vertex on an induced path in G between x and z. The ternary relations Bs(P){\cal B}_s(P) and Bs(G){\cal B}_s(G) are well-known examples of so-called strict betweennesses. We characterize the pairs (P,G) of posets P and graphs G on the same ground set V which induce the same strict betweenness relation Bs(P)=Bs(G){\cal B}_s(P)={\cal B}_s(G). 相似文献