On the complete digraphs which are simply disconnected.
Homotopic methods are employed for the characterization of the complete digraphs which are the composition of non-trivial highly regular tournaments.
On the completeness of decomposable properties of graphs
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 has the property , 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 completion of incomplete latin squares.
On the complexity of covering nodes by K node-disjoint cycles
On the Complexity of Reinforcement in Graphs
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
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 complexity of the subgraph problem
On the composition factors of a group with the same prime graph as
Let be a finite group. The prime graph of is a graph whose vertex set is the set of prime divisors of and two distinct primes and are joined by an edge, whenever contains an element of order . The prime graph of is denoted by . It is proved that some finite groups are uniquely determined by their prime graph. In this paper, we show that if is a finite group such that , where , then has a unique nonabelian composition factor isomorphic to or .
On the computational complexity of (O,P)-partition problems
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 Cone of Nonnegative Circuits.
On the connection between the theory of signal flow graphs and the theory of directed graphs
On the Connectivities of Finite and Infinite Graphs.
On the connectivity of graphs embedded in surfaces. II.
On the connectivity of skeletons of pseudomanifolds with boundary
In this note we show that -skeletons and -skeletons of -pseudomanifolds with full boundary are -connected graphs and -connected -complexes, respectively. This generalizes previous results due to Barnette and Woon.
On the Connectivity of Total Graphs.
On the Construction and Characterisation of a Class of Designs.
On the construction of cyclic quadruple systems
On the construction of non-isomorphic Steiner quadruple systems
On the Contact Dimension of Graphs.
On the convex hull of projective planes
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.