Search results for " graph"

The Bishop–Phelps–Bollobás theorem for operators

2008

AbstractWe prove the Bishop–Phelps–Bollobás theorem for operators from an arbitrary Banach space X into a Banach space Y whenever the range space has property β of Lindenstrauss. We also characterize those Banach spaces Y for which the Bishop–Phelps–Bollobás theorem holds for operators from ℓ1 into Y. Several examples of classes of such spaces are provided. For instance, the Bishop–Phelps–Bollobás theorem holds when the range space is finite-dimensional, an L1(μ)-space for a σ-finite measure μ, a C(K)-space for a compact Hausdorff space K, or a uniformly convex Banach space.

A class of finite groups having nilpotent injectors

1986

AbstractThe purpose of this paper is to construct a class of groups which properly contains the class of N-constrained groups, and which is such that all groups in this class have N-injectors.

Estimating the length of minimal spanning trees in compression of files

1984

Compression of a formatted file by a minimal spanning tree (MST) is studied. Here the records of the file are considered as the nodes of a weighted undirected graph. Each record pair is connected in the graph and the corresponding arc is weighted by the sum of field lengths of those fields which differ in the two records. The actual compression is made by constructing an MST of the graph and by storing it in an economic way to preserve the information of the file. The length of the MST is a useful measure in the estimation of the power of the compression. In the paper we study upper bounds of this length, especially in the case where the field lengths of the different fields may vary. The u…

Minimum node weight spanning trees searching algorithm for broadcast transmission in sensor networks

2017

A minimum node weight spanning tree in a weighted, directed graph is a tree whose node with maximum out-weight is minimal among all spanning trees. This type of trees are important because they appear in the solutions of the maximum lifetime broadcasting problem in wireless sensor networks. In a complete graph build of N nodes there are NN-2 spanning trees and to find such trees it is necessary to perform more than O(NN-2) operations. In this paper we propose an algorithm for searching the minimum node weight spanning trees in the graph. In the proposed algorithm, instead of calculating the symbolic determinant of the generalized Laplacian matrix, numerical operations on its exponents are p…

Discrete Derivatives for Atom-Pairs as a Novel Graph-Theoretical Invariant for Generating New Molecular Descriptors: Orthogonality, Interpretation an…

2013

This report presents a new mathematical method based on the concept of the derivative of a molecular graph (G) with respect to a given event (S) to codify chemical structure information. The derivate over each pair of atoms in the molecule is defined as ∂G/∂S(vi  , vj )=(fi -2fij +fj )/fij , where fi (or fj ) and fij are the individual frequency of atom i (or j) and the reciprocal frequency of the atoms i and j, respectively. These frequencies characterize the participation intensity of atom pairs in S. Here, the event space is composed of molecular sub-graphs which participate in the formation of the G skeleton that could be complete (representing all possible connected sub-graphs) or comp…

A dual of 4-regular graph forG × C2n

2003

Abstract A graph is said h-decomposable if its edge-set is decomposable into edge-disjoint hamiltonian cycles. Jha [3] conjectured that if G is a non-bipartite h-decomposable graph on even number of vertices, then G × K2 is h-decomposable. We use the notion of dual graph defined in [4], we prove that if G = Q1,2 ⊕ C3,4 is a 4-regular non-bipartite h-decomposable graph and the dual graphs relative to Q1,2 and C3,4 are connected then G × K 2 and G × C 2n are h-decomposable (where C 2n is an even cycle).

Graph languages defined by systems of forbidden structures: A survey

1988

This paper deals with different ways of defining graph languages. These are the so-called forbidden structures. Some results on decision problems, their complexity, and set theoretic closure properties are scetched. A normal form, the minimal systems, are given. Finally the influence of the different kinds of forbidden structures on the descriptive power of the systems is shown.

Relations between structure and estimators in networks of dynamical systems

2011

The article main focus is on the identification of a graphical model from time series data associated with different interconnected entities. The time series are modeled as realizations of stochastic processes (representing nodes of a graph) linked together via transfer functions (representing the edges of the graph). Both the cases of non-causal and causal links are considered. By using only the measurements of the node outputs and without assuming any prior knowledge of the network topology, a method is provided to estimate the graph connectivity. In particular, it is proven that the method determines links to be present only between a node and its “kins”, where kins of a node consist of …

Extremal minimality conditions on automata

2012

AbstractIn this paper we investigate the minimality problem of DFAs by varying the set of final states. In other words, we are interested on how the choice of the final states can affect the minimality of the automata. The state-pair graph is a useful tool to investigate such a problem. The choice of a set of final states for the automaton A defines a coloring of the closed components of the state-pair graph and the minimality of A corresponds to a property of these colored components. A particular attention is devoted to the analysis of some extremal cases such as, for example, the automata that are minimal for any choice of the subset of final states F from the state set Q of the automato…

A note on the closed graph theorem

1977