On a code problem concerning planar acyclic graphs
On a generalization of perfect -matching
The paper is concerned with the existence of non-negative or positive solutions to , where is the vertex-edge incidence matrix of an undirected graph. The paper gives necessary and sufficient conditions for the existence of such a solution.
On bandwidth, cutwidth, and quotient graphs
On computing the distinguishing numbers of trees and forests.
On external-memory planar depth first search.
On -pairable graphs from trees
The concept of the -pairable graphs was introduced by Zhibo Chen (On -pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter , called the pair length of a graph , as the maximum such that is -pairable and if is not -pairable for any positive integer . In this paper, we answer the two open questions raised by Chen in the case that the graphs involved...
On linear layouts of graphs.
On locating a single path-like facility in a general graph
On location problems on fuzzy graphs.
Location problems concern a wide set of fields where it is usually assumed that exact data are known. However, in real applications, the location of the facility considered can be full of linguistic vagueness, that can be appropriately modeled using networks with fuzzy values. In that way arise Fuzzy Location Problems; this paper deals with their general formulation and the description solution methods. Namely we show the variety of problems that can be considered in this context and, for some of...
On Minimum and Maximum Spanning Trees of Linearly Moving Points.
On planar mixed hypergraphs.
On polynomial time decidability of induced-minor-closed classes
On sampling colorings of bipartite graphs.
On some Interconnections Between Combinatorial Optimization and Extremal Graph Theory
On subgraphs without large components
We consider, for a positive integer , induced subgraphs in which each component has order at most . Such a subgraph is said to be -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for -coloring...
On the approximation of min split-coloring and min cocoloring.
On the complexity of covering nodes by K node-disjoint cycles
On the complexity of the subgraph problem
On the computational complexity of centers locating in a graph
It is shown that the problem of finding a minimum -basis, the -center problem, and the -median problem are -complete even in the case of such communication networks as planar graphs with maximum degree 3. Moreover, a near optimal -center problem is also -complete.
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.