A lower bound for Schur numbers and multicolor Ramsey numbers.
A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs
For a connected graph and a set with at least two vertices, an -Steiner tree is a subgraph of that is a tree with . If the degree of each vertex of in is equal to 1, then is called a pendant -Steiner tree. Two -Steiner trees are internally disjoint if they share no vertices other than and have no edges in common. For and , the pendant tree-connectivity is the maximum number of internally disjoint pendant -Steiner trees in , and for , the -pendant tree-connectivity ...
A lower bound for the irredundance number of trees
Let ir(G) and γ(G) be the irredundance number and domination number of a graph G, respectively. The number of vertices and leaves of a graph G are denoted by n(G) and n₁(G). If T is a tree, then Lemańska [4] presented in 2004 the sharp lower bound γ(T) ≥ (n(T) + 2 - n₁(T))/3. In this paper we prove ir(T) ≥ (n(T) + 2 - n₁(T))/3. for an arbitrary tree T. Since γ(T) ≥ ir(T) is always valid, this inequality is an extension and improvement of Lemańska's result. ...
A lower bound for the number of distinct eigenvalues of some real symmetric matrices.
A lower bound for the number of edges in a graph containing no two cycles of the same length.
A Lower Bound for the Optimal Crossing-Free Hamiltonian Cycle Problem.
A lower bound for the packing chromatic number of the Cartesian product of cycles
Let G = (V, E) be a simple graph of order n and i be an integer with i ≥ 1. The set X i ⊆ V(G) is called an i-packing if each two distinct vertices in X i are more than i apart. A packing colouring of G is a partition X = {X 1, X 2, …, X k} of V(G) such that each colour class X i is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by χρ(G). In this paper we show, using a theoretical proof, that if q = 4t, for some integer t ≥ 3, then 9...
A lower bound on the independence number of a graph in terms of degrees
For a connected and non-complete graph, a new lower bound on its independence number is proved. It is shown that this bound is realizable by the well known efficient algorithm MIN.
A magical approach to some labeling conjectures
In this paper, a complete characterization of the (super) edge-magic linear forests with two components is provided. In the process of establishing this characterization, the super edge-magic, harmonious, sequential and felicitous properties of certain 2-regular graphs are investigated, and several results on super edge-magic and felicitous labelings of unions of cycles and paths are presented. These labelings resolve one conjecture on harmonious graphs as a corollary, and make headway towards the...
A Markov chain approach to randomly grown graphs.
A matching and a Hamiltonian cycle of the fourth power of a connected graph
The following result is proved: Let be a connected graph of order . Then for every matching in there exists a hamiltonian cycle of such that .
A matrix representation of graphs and its spectrum as a graph invariant.
A Matroid on Hypergraphs, with Applications in Scene Analysis and Geometry.
A Maximal Toroidal Graph which is not a Triangulation.
A maximum degree theorem for diameter-2-critical graphs
A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ⌊n 2/4⌋ and that the extremal graphs are the complete bipartite graphs K ⌊n/2⌋,⌊n/2⌉. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n 0 where n 0 is a...
A Maximum Resonant Set of Polyomino Graphs
A polyomino graph P is a connected finite subgraph of the infinite plane grid such that each finite face is surrounded by a regular square of side length one and each edge belongs to at least one square. A dimer covering of P corresponds to a perfect matching. Different dimer coverings can interact via an alternating cycle (or square) with respect to them. A set of disjoint squares of P is a resonant set if P has a perfect matching M so that each one of those squares is M-alternating. In this paper,...
A measure of graph vulnerability: Scattering number.
A Metaheuristic Approach to Solving the Generalized Vertex Cover Problem
AMS Subj. Classification: 90C27, 05C85, 90C59The topic is related to solving the generalized vertex cover problem (GVCP) by genetic algorithm. The problem is NP-hard as a generalization of well-known vertex cover problem which was one of the first problems shown to be NP-hard. The definition of the GVCP and basics of genetic algorithms are described. Details of genetic algorithm and numerical results are presented in [8]. Genetic algorithm obtained high quality solutions in a short period of time.
A method of constructing the frame of a directed graph
In web search engines, such as Google, the ranking of a particular keyword is determined by mathematical tools, e.g., Pagerank or Hits. However, as the size of the network increases, it becomes increasingly difficult to use keyword ranking to quickly find the information required by an individual user. One reason for this phenomenon is the interference of superfluous information with the link structure. The World Wide Web can be expressed as an enormous directed graph. The purpose of the present...
A metric for graphs