Ground state incongruence in 2D spin glasses revisited.
Higher-order Lucas numbers.
Hyperenergetic and Hypoenergetic Graphs
Inequalities involving independence domination, -domination, connected and total -domination numbers
Let be an integer-valued function defined on the vertex set of a graph . A subset of is an -dominating set if each vertex outside is adjacent to at least vertices in . The minimum number of vertices in an -dominating set is defined to be the -domination number, denoted by . In a similar way one can define the connected and total -domination numbers and . If for all vertices , then these are the ordinary domination number, connected domination number and total domination...
Laplacian matrix and distance in trees
Markov chain small-world model with asymmetric transition probabilities.
Modified Wiener indices of thorn trees
Monomial subdigraphs of reachable and controllable positive discrete-time systems
A generic structure of reachable and controllable positive linear systems is given in terms of some characteristic components (monomial subdigraphs) of the digraph of a non-negative a pair. The properties of monomial subdigraphs are examined and used to derive reachability and controllability criteria in a digraph form for the general case when the system matrix may contain zero columns. The graph-theoretic nature of these criteria makes them computationally more efficient than their known equivalents....
Nanonetworks: The graph theory framework for modeling nanoscale systems
Nanonetwork is defined as a mathematical model of nanosize objects with biological, physical and chemical attributes, which are interconnected within certain dynamical process. To demonstrate the potentials of this modeling approach for quantitative study of complexity at nanoscale, in this survey, we consider three kinds of nanonetworks: Genes of a yeast are connected by weighted links corresponding to their coexpression along the cell cycle; Gold nanoparticles, arranged on a substrate, are linked...
Nearly complete graphs decomposable into large induced matchings and their applications
We describe two constructions of (very) dense graphs which are edge disjoint unions of large induced matchings. The first construction exhibits graphs on vertices with edges, which can be decomposed into pairwise disjoint induced matchings, each of size . The second construction provides a covering of all edges of the complete graph by two graphs, each being the edge disjoint union of at most induced matchings, where . This disproves (in a strong form) a conjecture of Meshulam, substantially...
Node assignment problem in Bayesian networks
This paper deals with the problem of searching for the best assignments of random variables to nodes in a Bayesian network (BN) with a given topology. Likelihood functions for the studied BNs are formulated, methods for their maximization are described and, finally, the results of a study concerning the reliability of revealing BNs' roles are reported. The results of BN node assignments can be applied to problems of the analysis of gene expression profiles.
Nordhaus-Gaddum-Type Results for Resistance Distance-Based Graph Invariants
Two decades ago, resistance distance was introduced to characterize “chemical distance” in (molecular) graphs. In this paper, we consider three resistance distance-based graph invariants, namely, the Kirchhoff index, the additive degree-Kirchhoff index, and the multiplicative degree-Kirchhoff index. Some Nordhaus-Gaddum-type results for these three molecular structure descriptors are obtained. In addition, a relation between these Kirchhoffian indices is established.
Nullity of Graphs
Nullity of Graphs: An Updated Survey
Odd-vertex-degree trees maximizing Wiener index
Offensive alliances in graphs
A set S is an offensive alliance if for every vertex v in its boundary N(S)- S it holds that the majority of vertices in v's closed neighbourhood are in S. The offensive alliance number is the minimum cardinality of an offensive alliance. In this paper we explore the bounds on the offensive alliance and the strong offensive alliance numbers (where a strict majority is required). In particular, we show that the offensive alliance number is at most 2/3 the order and the strong offensive alliance number...
On a matching distance between rooted phylogenetic trees
The Robinson-Foulds (RF) distance is the most popular method of evaluating the dissimilarity between phylogenetic trees. In this paper, we define and explore in detail properties of the Matching Cluster (MC) distance, which can be regarded as a refinement of the RF metric for rooted trees. Similarly to RF, MC operates on clusters of compared trees, but the distance evaluation is more complex. Using the graph theoretic approach based on a minimum-weight perfect matching in bipartite graphs, the values...
On bounded paradoxical subsets of the plane
On connections between hypergraphs and algebras
The aim of the present paper is to translate some algebraic concepts to hypergraphs. Thus we obtain a new language, very useful in the investigation of subalgebra lattices of partial, and also total, algebras. In this paper we solve three such problems on subalgebra lattices, other will be solved in [[Pio4]]. First, we show that for two arbitrary partial algebras, if their directed hypergraphs are isomorphic, then their weak, relative and strong subalgebra lattices are isomorphic. Secondly, we prove...
On Fully Split Lacunary Polynomials in Finite Fields
We estimate the number of possible degree patterns of k-lacunary polynomials of degree t < p which split completely modulo p. The result is based on a combination of a bound on the number of zeros of lacunary polynomials with some graph theory arguments.