A remark on systems of maximal cliques of a graph
A remark on the (2,2)-domination number
A subset D of the vertex set of a graph G is a (k,p)-dominating set if every vertex v ∈ V(G)∖D is within distance k to at least p vertices in D. The parameter denotes the minimum cardinality of a (k,p)-dominating set of G. In 1994, Bean, Henning and Swart posed the conjecture that for any graph G with δₖ(G) ≥ k+p-1, where the latter means that every vertex is within distance k to at least k+p-1 vertices other than itself. In 2005, Fischermann and Volkmann confirmed this conjecture for all integers...
A remark on -regular orthomodular lattices
A finite orthomodular lattice in which every maximal Boolean subalgebra (block) has the same cardinality is called -regular, if each atom is a member of just blocks. We estimate the minimal number of blocks of -regular orthomodular lattices to be lower than of equal to regardless of .
A reminiscence about shortest spanning subtrees
A restricted random walk defined via a Fibonacci process.
A result on co-chromatic graphs.
A result on -critical graphs.
A result related to the largest eigenvalue of a tree
In this note we prove that {0,1,√2,√3,2} is the set of all real numbers l such that the following holds: every tree having an eigenvalue which is larger than l has a subtree whose largest eigenvalue is l.
A service points location problem with Min-Max distance optimality criterion
A sharp bound for the reconstruction of partitions.
A sharp upper bound for the spectral radius of a nonnegative matrix and applications
We obtain a sharp upper bound for the spectral radius of a nonnegative matrix. This result is used to present upper bounds for the adjacency spectral radius, the Laplacian spectral radius, the signless Laplacian spectral radius, the distance spectral radius, the distance Laplacian spectral radius, the distance signless Laplacian spectral radius of an undirected graph or a digraph. These results are new or generalize some known results.
A short proof of a theorem of Kano and Yu on factors in regular graphs.
A short proof of rigidity of convex polytopes.
A shorter proof of the distance energy of complete multipartite graphs
Caporossi, Chasser and Furtula in [Les Cahiers du GERAD (2009) G-2009-64] conjectured that the distance energy of a complete multipartite graph of order n with r ≥ 2 parts, each of size at least 2, is equal to 4(n − r). Stevanovic, Milosevic, Hic and Pokorny in [MATCH Commun. Math. Comput. Chem. 70 (2013), no. 1, 157-162.] proved the conjecture, and then Zhang in [Linear Algebra Appl. 450 (2014), 108-120.] gave another proof. We give a shorter proof of this conjecture using the interlacing inequalities...
A simple algorithm for constructing Szemerédi's regularity partition.
A simple bijection between binary trees and colored ternary trees.
A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs.
A simple linear algorithm for the connected domination problem in circular-arc graphs
A connected dominating set of a graph G = (V,E) is a subset of vertices CD ⊆ V such that every vertex not in CD is adjacent to at least one vertex in CD, and the subgraph induced by CD is connected. We show that, given an arc family F with endpoints sorted, a minimum-cardinality connected dominating set of the circular-arc graph constructed from F can be computed in O(|F|) time.
A simple method for constructing small cubic graphs of girths 14, 15, and 16.
A simple proof of a theorem by Tutte.