All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 17 Next

Displaying 321 – 340 of 663

Showing per page

Comparing Imperfection Ratio and Imperfection Index for Graph Classes

Arie M.C.A. Koster, Annegret K. Wagler (2009)

RAIRO - Operations Research

Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs G where the stable set polytope STAB(G) coincides with the fractional stable set polytope QSTAB(G). For all imperfect graphs G it holds that STAB(G) ⊂ QSTAB(G). It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away...

Comparison of algorithms in graph partitioning

Alain Guénoche (2008)

RAIRO - Operations Research - Recherche Opérationnelle

We first describe four recent methods to cluster vertices of an undirected non weighted connected graph. They are all based on very different principles. The fifth is a combination of classical ideas in optimization applied to graph partitioning. We compare these methods according to their ability to recover classes initially introduced in random graphs with more edges within the classes than between them.

Comparison of algorithms in graph partitioning

Alain Guénoche (2009)

RAIRO - Operations Research

We first describe four recent methods to cluster vertices of an undirected non weighted connected graph. They are all based on very different principles. The fifth is a combination of classical ideas in optimization applied to graph partitioning. We compare these methods according to their ability to recover classes initially introduced in random graphs with more edges within the classes than between them.

Comparison of Metric Spectral Gaps

Assaf Naor (2014)

Analysis and Geometry in Metric Spaces

Let A = (aij) ∊ Mn(ℝ) be an n by n symmetric stochastic matrix. For p ∊ [1, ∞) and a metric space (X, dX), let γ(A, dpx) be the infimum over those γ ∊ (0,∞] for which every x1, . . . , xn ∊ X satisfy [...] Thus γ (A, dpx) measures the magnitude of the nonlinear spectral gap of the matrix A with respect to the kernel dpX : X × X →[0,∞). We study pairs of metric spaces (X, dX) and (Y, dY ) for which there exists Ψ: (0,∞)→(0,∞) such that γ (A, dpX) ≤Ψ (A, dpY ) for every symmetric stochastic A ∊ Mn(ℝ)...

Competition hypergraphs of digraphs with certain properties II. Hamiltonicity

Martin Sonntag, Hanns-Martin Teichert (2008)

Discussiones Mathematicae Graph Theory

If D = (V,A) is a digraph, its competition hypergraph (D) has vertex set V and e ⊆ V is an edge of (D) iff |e| ≥ 2 and there is a vertex v ∈ V, such that e = N D ⁻ ( v ) = w ∈ V | ( w , v ) ∈ A . We give characterizations of (D) in case of hamiltonian digraphs D and, more general, of digraphs D having a τ-cycle factor. The results are closely related to the corresponding investigations for competition graphs in Fraughnaugh et al. [4] and Guichard [6].

Competition hypergraphs of digraphs with certain properties I. Strong connectedness

Martin Sonntag, Hanns-Martin Teichert (2008)

Discussiones Mathematicae Graph Theory

If D = (V,A) is a digraph, its competition hypergraph 𝓒𝓗(D) has the vertex set V and e ⊆ V is an edge of 𝓒𝓗(D) iff |e| ≥ 2 and there is a vertex v ∈ V, such that e = {w ∈ V|(w,v) ∈ A}. We tackle the problem to minimize the number of strong components in D without changing the competition hypergraph 𝓒𝓗(D). The results are closely related to the corresponding investigations for competition graphs in Fraughnaugh et al. [3].

Complete arcs arising from a generalization of the Hermitian curve

Herivelto Borges, Beatriz Motta, Fernando Torres (2014)

Acta Arithmetica

We investigate complete arcs of degree greater than two, in projective planes over finite fields, arising from the set of rational points of a generalization of the Hermitian curve. The degree of the arcs is closely related to the number of rational points of a class of Artin-Schreier curves, which is calculated by using exponential sums via Coulter's approach. We also single out some examples of maximal curves.

Complete minors, independent sets, and chordal graphs

József Balogh, John Lenz, Hehui Wu (2011)

Discussiones Mathematicae Graph Theory

The Hadwiger number h(G) of a graph G is the maximum size of a complete minor of G. Hadwiger's Conjecture states that h(G) ≥ χ(G). Since χ(G) α(G) ≥ |V(G)|, Hadwiger's Conjecture implies that α(G) h(G) ≥ |V(G)|. We show that (2α(G) - ⌈log_{τ}(τα(G)/2)⌉) h(G) ≥ |V(G)| where τ ≍ 6.83. For graphs with α(G) ≥ 14, this improves on a recent result of Kawarabayashi and Song who showed (2α(G) - 2) h(G) ≥ |V(G) | when α(G) ≥ 3.

Completely dissociative groupoids

Milton Braitt, David Hobby, Donald Silberger (2012)

Mathematica Bohemica

In a groupoid, consider arbitrarily parenthesized expressions on the k variables x 0 , x 1 , ⋯ x k - 1 where each x i appears once and all variables appear in order of their indices. We call these expressions k -ary formal products, and denote the set containing all of them by F σ ( k ) . If u , v ∈ F σ ( k ) are distinct, the statement that u and v are equal for all values of x 0 , x 1 , ⋯ x k - 1 is a generalized associative law. Among other results, we show that many small groupoids are completely dissociative, meaning that no generalized associative law holds...

Currently displaying 321 – 340 of 663