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 Contact Dimension of Graphs.
On the Corona of Two Graphs.
On the Corona of Two Graphs. (Short Communication).
On the cost chromatic number of outerplanar, planar, and line graphs
We consider vertex colorings of graphs in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of the coloring is the sum of the costs incurred at each vertex. The cost chromatic number of a graph with respect to a cost set is the minimum number of colors necessary to produce a minimum cost coloring of the graph. We show that the cost chromatic number of maximal outerplanar and maximal planar graphs can be arbitrarily large and construct...
On the crossing number of .
On the Crossing Numbers of Cartesian Products of Stars and Graphs of Order Six
The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of G in the plane. According to their special structure, the class of Cartesian products of two graphs is one of few graph classes for which some exact values of crossing numbers were obtained. The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. Moreover, except of six graphs, the crossing numbers of Cartesian products G⃞K1,n for all other...
On the crossing numbers of Cartesian products of stars and paths or cycles
On the Crossing Numbers of Cartesian Products of Wheels and Trees
Bokal developed an innovative method for finding the crossing numbers of Cartesian product of two arbitrarily large graphs. In this article, the crossing number of the join product of stars and cycles are given. Afterwards, using Bokal’s zip product operation, the crossing numbers of the Cartesian products of the wheel Wn and all trees T with maximum degree at most five are established.