On Arbitrarily Traceable Graphs.
On arbitrarily vertex decomposable unicyclic graphs with dominating cycle
A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,...,nₖ) of positive integers such that , there exists a partition (V₁,...,Vₖ) of vertex set of G such that for every i ∈ 1,...,k the set induces a connected subgraph of G on vertices. We consider arbitrarily vertex decomposable unicyclic graphs with dominating cycle. We also characterize all such graphs with at most four hanging vertices such that exactly two of them have a common neighbour.
On Certain Edge-Critical Graphs of a Given Diameter
On Certain Homomorphism Properties of Graphs I.
On certain regular graphs of girth 5.
On classes of graphs determined by forbidden subgraphs
On critical and cocritical radius edge-invariant graphs
The concepts of critical and cocritical radius edge-invariant graphs are introduced. We prove that every graph can be embedded as an induced subgraph of a critical or cocritical radius-edge-invariant graph. We show that every cocritical radius-edge-invariant graph of radius r ≥ 15 must have at least 3r+2 vertices.
On cyclically embeddable graphs
An embedding of a simple graph G into its complement G̅ is a permutation σ on V(G) such that if an edge xy belongs to E(G), then σ(x)σ(y) does not belong to E(G). In this note we consider some families of embeddable graphs such that the corresponding permutation is cyclic.
On degrees in the hasse diagram of the strong Bruhat order.
On directed triangles in digraphs.
On dominating the Cartesian product of a graph and K₂
In this paper we consider the Cartesian product of an arbitrary graph and a complete graph of order two. Although an upper and lower bound for the domination number of this product follow easily from known results, we are interested in the graphs that actually attain these bounds. In each case, we provide an infinite class of graphs to show that the bound is sharp. The graphs that achieve the lower bound are of particular interest given the special nature of their dominating sets and are investigated...
On edge independence numbers and edge covering numbers of -uniform hypergraph
On equality of edge-connectivity and minimum degree of a graph
On extremal graphs with no long paths.
On extremal sizes of locally -tree graphs
A graph is a locally -tree graph if for any vertex the subgraph induced by the neighbours of is a -tree, , where -tree is an edgeless graph, -tree is a tree. We characterize the minimum-size locally -trees with vertices. The minimum-size connected locally -trees are simply -trees. For , we construct locally -trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an -vertex locally -tree graph is between and , where both...
On -domination number of a graph
On families of weakly dependent random variables
Let be a family of random independent k-element subsets of [n] = 1,2,...,n and let denote a family of ℓ-element subsets of [n] such that the event that S belongs to depends only on the edges of contained in S. Then, the edges of are ’weakly dependent’, say, the events that two given subsets S and T are in are independent for vast majority of pairs S and T. In the paper we present some results on the structure of weakly dependent families of subsets obtained in this way. We also list...
On four-point boundary value problems for differential inclusions and differential equations with and without multivalued moving constraints
We deal with the problems of four boundary points conditions for both differential inclusions and differential equations with and without moving constraints. Using a very recent result we prove existence of generalized solutions for some differential inclusions and some differential equations with moving constraints. The results obtained improve the recent results obtained by Papageorgiou and Ibrahim-Gomaa. Also by means of a rather different approach based on an existence theorem due to O. N. Ricceri...
On graphs with cyclic defect or excess.
On graphs with maximum size in their switching classes
In his PhD thesis [Structural aspects of switching classes, Leiden Institute of Advanced Computer Science, 2001] Hage posed the following problem: “characterize the maximum size graphs in switching classes”. These are called s-maximal graphs. In this paper, we study the properties of such graphs. In particular, we show that any graph with sufficiently large minimum degree is s-maximal, we prove that join of two s-maximal graphs is also an s-maximal graph, we give complete characterization of triangle-free...