On the minimal length of the longest trail in a fixed edge-density graph
A nearly sharp lower bound on the length of the longest trail in a graph on n vertices and average degree k is given provided the graph is dense enough (k ≥ 12.5).
On the minimum degree and edge-connectivity of a graph
On the minimum number of vertices and edges in a graph with a given number of spanning trees
On the Non-(p−1)-Partite Kp-Free Graphs
We say that a graph G is maximal Kp-free if G does not contain Kp but if we add any new edge e ∈ E(G) to G, then the graph G + e contains Kp. We study the minimum and maximum size of non-(p − 1)-partite maximal Kp-free graphs with n vertices. We also answer the interpolation question: for which values of n and m are there any n-vertex maximal Kp-free graphs of size m?
On the number of cut-vertices in a graph.
On the number of orthogonal systems in vector spaces over finite fields.
On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs
A cut-vertex in a graph G is a vertex whose removal increases the number of connected components of G. An end-block of G is a block with a single cut-vertex. In this paper we establish upper bounds on the numbers of end-blocks and cut-vertices in a 4-regular graph G and claw-free 4-regular graphs. We characterize the extremal graphs achieving these bounds.
On the Ramsey-Turán number of finite graphs
On the resilience of long cycles in random graphs.
On the selection of pairs
On the size of minimal unsatisfiable formulas.
On the Spectral Radius of Connected Graphs
On the stability for pancyclicity
A property P defined on all graphs of order n is said to be k-stable if for any graph of order n that does not satisfy P, the fact that uv is not an edge of G and that G + uv satisfies P implies . Every property is (2n-3)-stable and every k-stable property is (k+1)-stable. We denote by s(P) the smallest integer k such that P is k-stable and call it the stability of P. This number usually depends on n and is at most 2n-3. A graph of order n is said to be pancyclic if it contains cycles of all lengths...
On the system of all maximal chains (antichains) of a graph.
On the Turán properties of infinite graphs.
On total restrained domination in graphs
In this paper we initiate the study of total restrained domination in graphs. Let be a graph. A total restrained dominating set is a set where every vertex in is adjacent to a vertex in as well as to another vertex in , and every vertex in is adjacent to another vertex in . The total restrained domination number of , denoted by , is the smallest cardinality of a total restrained dominating set of . First, some exact values and sharp bounds for are given in Section 2. Then the Nordhaus-Gaddum-type...
On vertex stability with regard to complete bipartite subgraphs
A graph G is called (H;k)-vertex stable if G contains a subgraph isomorphic to H ever after removing any of its k vertices. Q(H;k) denotes the minimum size among the sizes of all (H;k)-vertex stable graphs. In this paper we complete the characterization of -vertex stable graphs with minimum size. Namely, we prove that for m ≥ 2 and n ≥ m+2, and as well as are the only -vertex stable graphs with minimum size, confirming the conjecture of Dudek and Zwonek.
On -bounded families of graphs.
One-two descriptor of graphs
Optimal constructions of event-node networks