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...

Let G be a graph of order n, and let a and b be two integers with 1 ≤ a ≤ b. Let h : E(G) → [0, 1] be a function. If a ≤ ∑e∋x h(e) ≤ b holds for any x ∈ V (G), then we call G[Fh] a fractional [a, b]-factor of G with indicator function h, where Fh = {e ∈ E(G) : h(e) > 0}. A graph G is fractional independent-set-deletable [a, b]-factor-critical (in short, fractional ID-[a, b]- factor-critical) if G − I has a fractional [a, b]-factor for every independent set I of G. In this paper, it is proved...

The problem of finding minimal vertex number of graphs with a given automorphism group is addressed in this article for the case of cyclic groups. This problem was considered earlier by other authors. We give a construction of an undirected graph having $4n+6$ vertices and automorphism group cyclic of order $4n$, $n\ge 1$. As a special case we get graphs with $2^k+6$ vertices and cyclic automorphism groups of order $2^k$. It can revive interest in related problems.

We prove that every vertex v of a tournament T belongs to at least $maxmin\delta ⁺\left(T\right),2\delta ⁺\left(T\right)-d{⁺}_T\left(v\right)+1,min\delta ¯\left(T\right),2\delta ¯\left(T\right)-d{¯}_T\left(v\right)+1$ arc-disjoint cycles, where δ⁺(T) (or δ¯(T)) is the minimum out-degree (resp. minimum in-degree) of T, and $d{⁺}_T\left(v\right)$ (or $d{¯}_T\left(v\right)$) is the out-degree (resp. in-degree) of v.

Let G be a simple graph of order n and size e(G). It is well known that if e(G) ≤ n-2, then there is an edge-disjoint placement of two copies of G into Kₙ. We prove that with the same condition on size of G we have actually (with few exceptions) a careful packing of G, that is an edge-disjoint placement of two copies of G into Kₙ∖Cₙ.

A dominating set D of G is called a split dominating set of G if the subgraph induced by the subset V(G)-D is disconnected. The cardinality of a minimum split dominating set is called the minimum split domination number of G. Such subset and such number was introduced in [4]. In [2], [3] the authors estimated the domination number of products of graphs. More precisely, they were study products of paths. Inspired by those results we give another estimation of the domination number of the conjunction...

Let $L^a$ denote a set of additive hereditary graph properties. It is a known fact that a partially ordered set $(L^a,\subseteq )$ is a complete distributive lattice. We present results when a join of two additive hereditary graph properties in $(L^a,\subseteq )$ has a finite or infinite family of minimal forbidden subgraphs.

For a graph $G=(V,E)$, a double Roman dominating function is a function $f:V\to \{0,1,2,3\}$ having the property that if $f\left(v\right)=0$, then the vertex $v$ must have at least two neighbors assigned $2$ under $f$ or one neighbor with $f\left(w\right)=3$, and if $f\left(v\right)=1$, then the vertex $v$ must have at least one neighbor with $f\left(w\right)\ge 2$. The weight of a double Roman dominating function $f$ is the sum $f\left(V\right)={\sum }_{v\in V}f\left(v\right)$. The minimum weight of a double Roman dominating function on $G$ is called the double Roman domination number of $G$ and is denoted by ${\gamma }_{\mathrm{dR}}\left(G\right)$. In this paper, we establish a new upper bound...