A note on the Hamiltonian genus of a complete bipartite graph.
A note on the hardness results for the labeled perfect matching problems in bipartite graphs
In this note, we strengthen the inapproximation bound of O(logn) for the labeled perfect matching problem established in J. Monnot, The Labeled perfect matching in bipartite graphs, Information Processing Letters96 (2005) 81–88, using a self improving operation in some hard instances. It is interesting to note that this self improving operation does not work for all instances. Moreover, based on this approach we deduce that the problem does not admit constant approximation algorithms for connected...
A note on the independence number of an identically self-dual perfect matroid design.
A note on the independent domination number of subset graph
The independent domination number (independent number ) is the minimum (maximum) cardinality among all maximal independent sets of . Haviland (1995) conjectured that any connected regular graph of order and degree satisfies . For , the subset graph is the bipartite graph whose vertices are the - and -subsets of an element ground set where two vertices are adjacent if and only if one subset is contained in the other. In this paper, we give a sharp upper bound for and prove that...
A note on the independent domination number versus the domination number in bipartite graphs
Let and be the domination number and the independent domination number of , respectively. Rad and Volkmann posted a conjecture that for any graph , where is its maximum degree (see N. J. Rad, L. Volkmann (2013)). In this work, we verify the conjecture for bipartite graphs. Several graph classes attaining the extremal bound and graphs containing odd cycles with the ratio larger than are provided as well.
A note on the k-domination number of a graph.
A note on the largest eigenvalue of non-regular graphs.
A note on the modified -Bernstein polynomials.
A note on the non-colorability threshold of a random graph.
A note on the number of associative triples in finite commutative Moufang loops
A note on the number of derangements.
A note on the number of edges guaranteeing a in Eulerian bipartite digraphs.
A note on the number of Hamiltonian paths in strong tournaments.
A note on the number of squares in a partial word with one hole
A well known result of Fraenkel and Simpson states that the number of distinct squares in a word of length n is bounded by 2n since at each position there are at most two distinct squares whose last occurrence starts. In this paper, we investigate squares in partial words with one hole, or sequences over a finite alphabet that have a “do not know” symbol or “hole”. A square in a partial word over a given alphabet has the form uv where u is compatible with v, and consequently, such square is...
A note on the open packing number in graphs
A subset of vertices in a graph is an open packing set if no pair of vertices of has a common neighbor in . An open packing set which is not a proper subset of any open packing set is called a maximal open packing set. The maximum cardinality of an open packing set is called the open packing number and is denoted by . A subset in a graph with no isolated vertex is called a total dominating set if any vertex of is adjacent to some vertex of . The total domination number of , denoted...
A Note on the p−Center Problem
A Note on the Permanental Roots of Bipartite Graphs
It is well-known that any graph has all real eigenvalues and a graph is bipartite if and only if its spectrum is symmetric with respect to the origin. We are interested in finding whether the permanental roots of a bipartite graph G have symmetric property as the spectrum of G. In this note, we show that the permanental roots of bipartite graphs are symmetric with respect to the real and imaginary axes. Furthermore, we prove that any graph has no negative real permanental root, and any graph containing...
A Note on the Powers of 2-Connected Graphs.
A note on the problem of finding a (3,9)-cage.
A note on the -binomial rational root theorem.