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 42 Next

Displaying 821 – 840 of 1336

Showing per page

On the completeness of decomposable properties of graphs

Mariusz Hałuszczak, Pavol Vateha (1999)

Discussiones Mathematicae Graph Theory

Let ₁,₂ be additive hereditary properties of graphs. A (₁,₂)-decomposition of a graph G is a partition of E(G) into sets E₁, E₂ such that induced subgraph G [ E i ] has the property i , i = 1,2. Let us define a property ₁⊕₂ by G: G has a (₁,₂)-decomposition. A property D is said to be decomposable if there exists nontrivial additive hereditary properties ₁, ₂ such that D = ₁⊕₂. In this paper we determine the completeness of some decomposable properties and we characterize the decomposable properties of completeness...

On the Complexity of Reinforcement in Graphs

Nader Jafari Rad (2016)

Discussiones Mathematicae Graph Theory

We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.

On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs

Pavol Hell, César Hernández-Cruz (2014)

Discussiones Mathematicae Graph Theory

Let D be a digraph with the vertex set V (D) and the arc set A(D). A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V (D) − N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V (D). A 2-kernel is called a kernel. It is known that the problem of determining whether a digraph has a kernel (“the kernel problem”) is NP-complete, even in quite restricted...

On the composition factors of a group with the same prime graph as B n ( 5 )

Azam Babai, Behrooz Khosravi (2012)

Czechoslovak Mathematical Journal

Let G be a finite group. The prime graph of G is a graph whose vertex set is the set of prime divisors of | G | and two distinct primes p and q are joined by an edge, whenever G contains an element of order p q . The prime graph of G is denoted by Γ ( G ) . It is proved that some finite groups are uniquely determined by their prime graph. In this paper, we show that if G is a finite group such that Γ ( G ) = Γ ( B n ( 5 ) ) , where n ≥ 6 , then G has a unique nonabelian composition factor isomorphic to B n ( 5 ) or C n ( 5 ) .

On the computational complexity of (O,P)-partition problems

Jan Kratochvíl, Ingo Schiermeyer (1997)

Discussiones Mathematicae Graph Theory

We prove that for any additive hereditary property P > O, it is NP-hard to decide if a given graph G allows a vertex partition V(G) = A∪B such that G[A] ∈ 𝓞 (i.e., A is independent) and G[B] ∈ P.

On the connectivity of skeletons of pseudomanifolds with boundary

R. Ayala, M. J. Chávez, Alberto Márquez, Antonio Quintero (2002)

Mathematica Bohemica

In this note we show that 1 -skeletons and 2 -skeletons of n -pseudomanifolds with full boundary are ( n + 1 ) -connected graphs and n -connected 2 -complexes, respectively. This generalizes previous results due to Barnette and Woon.

On the convex hull of projective planes

Jean-François Maurras, Roumen Nedev (2008)

RAIRO - Operations Research

We study the finite projective planes with linear programming models. We give a complete description of the convex hull of the finite projective planes of order 2. We give some integer linear programming models whose solution are, either a finite projective (or affine) plane of order n, or a (n+2)-arc.

Currently displaying 821 – 840 of 1336