Upper bound for the energy of graphs with fixed second and fourth spectral moments
Using Lovász local lemma in the space of random injections.
Value-True Walks in Finite, Connected, Valuated Graphs.
Variable neighborhood search for extremal graphs. 17. Further conjectures and results about the index
The AutoGraphiX 2 system is used to compare the index of a connected graph G with a number of other graph theoretical invariants, i.e., chromatic number, maximum, minimum and average degree, diameter, radius, average distance, independence and domination numbers. In each case, best possible lower and upper bounds, in terms of the order of G, are sought for sums, differences, ratios and products of the index and another invariant. There are 72 cases altogether: in 7 cases known results were reproduced,...
Variations sur un algorithme de DANTZIG : application à la recherche des plus courts chemins dans les grands réseaux
Vertex Cyclic Graphs.
Vertex-disjoint stars in graphs
In this paper, we give a sufficient condition for a graph to contain vertex-disjoint stars of a given size. It is proved that if the minimum degree of the graph is at least k+t-1 and the order is at least (t+1)k + O(t²), then the graph contains k vertex-disjoint copies of a star . The condition on the minimum degree is sharp, and there is an example showing that the term O(t²) for the number of uncovered vertices is necessary in a sense.
Vertices contained in all minimum paired-dominating sets of a tree
A set of vertices in a graph is called a paired-dominating set if it dominates and contains at least one perfect matching. We characterize the set of vertices of a tree that are contained in all minimum paired-dominating sets of the tree.
Voltage graphs, group presentations and cages.
Weak Saturation Numbers for Sparse Graphs
For a fixed graph F, a graph G is F-saturated if there is no copy of F in G, but for any edge e ∉ G, there is a copy of F in G + e. The minimum number of edges in an F-saturated graph of order n will be denoted by sat(n, F). A graph G is weakly F-saturated if there is an ordering of the missing edges of G so that if they are added one at a time, each edge added creates a new copy of F. The minimum size of a weakly F-saturated graph G of order n will be denoted by wsat(n, F). The graphs of order...
Weakly P-saturated graphs
For a hereditary property let denote the number of forbidden subgraphs contained in G. A graph G is said to be weakly -saturated, if G has the property and there is a sequence of edges of G̅, say , such that the chain of graphs has the following property: , 0 ≤ i ≤ l-1. In this paper we shall investigate some properties of weakly saturated graphs. We will find upper bound for the minimum number of edges of weakly ₖ-saturated graphs of order n. We shall determine the number wsat(n,) for some...
Well covered and well dominated block graphs and unicyclic graphs.
Wiener index of graphs with fixed number of pendant or cut-vertices
The Wiener index of a connected graph is defined as the sum of the distances between all unordered pairs of its vertices. We characterize the graphs which extremize the Wiener index among all graphs on vertices with pendant vertices. We also characterize the graph which minimizes the Wiener index over the graphs on vertices with cut-vertices.
Zerlegung total gerichteter Graphen in Kreise.
Zur Minimalstruktur der nicht in die projektive Ebene einbettbaren Graphen.
Zweiseitig unendliche Züge in lokalendlichen Graphen
Алгоритм оптимального размещения медиан на дереве с вероятностными весами вершин
Доминирующие множества и гамильтоновость в -свободных графах.
Замечание о верхней оценке степени информационных графов
Локально Штрикханде графы и их автоморфизмы.