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

Page 1 Next

Displaying 1 – 20 of 46

Showing per page

On a generalization of perfect b -matching

Ľubica Šándorová, Marián Trenkler (1991)

Mathematica Bohemica

The paper is concerned with the existence of non-negative or positive solutions to A f = β , where A 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 k -pairable graphs from trees

Zhongyuan Che (2007)

Czechoslovak Mathematical Journal

The concept of the k -pairable graphs was introduced by Zhibo Chen (On k -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 p ( G ) , called the pair length of a graph G , as the maximum k such that G is k -pairable and p ( G ) = 0 if G is not k -pairable for any positive integer k . In this paper, we answer the two open questions raised by Chen in the case that the graphs involved...

On location problems on fuzzy graphs.

José A. Moreno Pérez, J. Marcos Moreno-Vega, José Luis Verdegay (2001)

Mathware and Soft Computing

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 subgraphs without large components

Glenn G. Chappell, John Gimbel (2017)

Mathematica Bohemica

We consider, for a positive integer k , induced subgraphs in which each component has order at most k . Such a subgraph is said to be k -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 k -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for 2 -coloring...

On the computational complexity of centers locating in a graph

Ján Plesník (1980)

Aplikace matematiky

It is shown that the problem of finding a minimum k -basis, the n -center problem, and the p -median problem are N P -complete even in the case of such communication networks as planar graphs with maximum degree 3. Moreover, a near optimal m -center problem is also N P -complete.

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.

Currently displaying 1 – 20 of 46

Page 1 Next