In this paper, we study the upper bounds for the \(D(\beta)\)-vertex-distinguishing total-chromatic numbers using the probability method, and obtain: Let \(\Delta\) be the maximum degree of \(G\), then

\[
\chi_{\beta vt}\leq
\left\{
\begin{array}{ll}
16\Delta^{(\beta+1)/(2\Delta+2)}, & \Delta \geq 3,\beta\geq 4\Delta+3; \\
13\Delta^{(\beta+4)/4} , & \Delta\geq 4,\beta\geq 5;\\
10\Delta^2, & \Delta \geq 3, 2 \leq \beta \leq 4.
\end{array}
\right.
\]

Given a tournament \(T = (V, A)\), a subset \(X\) of \(V\) is an interval of \(T\) provided that for any \(a, b \in X\) and \(x \in V \setminus X\), \((a, x) \in A\) if and only if \((b, x) \in A\). For example, \(\emptyset\), \(\{x\}\) (\(x \in V\)), and \(V\) are intervals of \(T\), called trivial intervals. A two-element interval of \(T\) is called a duo of \(T\). Tournaments that do not admit any duo are called duo-free tournaments. A vertex \(x\) of a duo-free tournament is \(d\)-critical if \(T – x\) has at least one duo. In 2005, J.F. Culus and B. Jouve [5] characterized the duo-free tournaments, all of whose vertices are d-critical, called tournaments without acyclic interval. In this paper, we characterize the duo-free tournaments that admit exactly one non-d-critical vertex, called (-1)-critically duo-free tournaments.

The toughness, as the parameter for measuring stability and vulnerability of networks, has been widely used in computer communication
networks and ontology graph structure analysis. A graph \(G\) is called a fractional \((a, b, n)\)-critical deleted graph if after deleting any \(n\) vertices from \(G\), the resulting graph is still a fractional \((a, b)\)-deleted graph. In this paper,we study the relationship between toughness and fractional \((a, b, n)\)-critical deleted graph. A sufficient condition for a graph G to be a fractional \((a, b, n)\)-critical deleted graph is determined.

The Classification Problem is the problem of deciding whether a simple graph has chromatic index equal to \(\Delta\) or \(\Delta + 1\), where \(\Delta\) is the maximum degree of the graph. It is known that deciding if a graph has chromatic index equal to \(4\) is \(NP\)-complete. A split graph is a graph whose vertex set admits a partition into a stable set and a clique. The chromatic indexes for some subsets of split graphs, such as split graphs with odd maximum degree and split-indifference graphs, are known. However, for the general class, the problem remains unsolved. In this paper, we exhibit a new subset of split graphs with even maximum degree that have chromatic index equal to \(\Delta\). Moreover, we present polynomial-time algorithms to perform an edge-coloring and to recognize these graphs.

Let \(K_4^-\) be the graph obtained from \(K_4\) by deleting one edge. A graph \(G\) is called \(K_4^-\)-free if it does not contain \(K_4^-\) as a subgraph. K. Kawarabayashi showed that a \(K_4^-\)-free \(k\)-connected graph has a \(k\)-contractible edge if \(k\) is odd. Furthermore, when \(k\) is even, K. Ando et al. demonstrated that every vertex of a \(K_4^-\)-free contraction critical \(k\)-connected graph is contained in at least two triangles. In this paper, we extend Kawarabayashi’s result and obtain a new lower bound on the number of \(k\)-contractible edges in a \(K_4^-\)-free \(k\)-connected graph when \(k\) is odd. Additionally, we provide characterizations and properties of \(K_4^-\)-free contraction critical \(k\)-connected graphs and prove that such graphs have at least \(\frac{2|G|}{k-1}\) vertices of degree \(k\).

Let \(D\) be a directed graph with \(n\) vertices and \(m\) edges. A function \(f: V(D) \to \{1, 2, 3, \ldots, k\}\), where \(k \leq n\), is said to be a harmonious coloring of \(D\) if for any two edges \(xy\) and \(uv\) of \(D\), the ordered pair \((f(x), f(y)) \neq (f(u), f(v))\). If the pair \((i, i)\) is not assigned, then \(f\) is said to be a proper harmonious coloring of \(D\). The minimum \(k\) is called the proper harmonious coloring number of \(D\). We investigate the proper harmonious coloring number of various graphs, including unidirectional paths, unicycles, inward-spoken (outward-spoken) wheels, \(n\)-ary trees of different levels, and others.

A vertex subset \(S\) of a digraph \(D = (V, A)\) is called an out-dominating (resp.,in-dominating) set of \(D\) if every vertex in \(V – S\) is adjacent from (resp., to) some vertex in \(S\). The out-domination (resp., in-domination) number of \(D\), denoted by \(\gamma^+(D)\) (resp.,\(\gamma^-(D)\)), is the minimum cardinality of an out-dominating (resp., in-dominating) set of \(D\). In 1999, Chartrand et al. proved that \(\gamma^+(D) + \gamma^-(D) \leq \frac{4n}{3}\) for every digraph \(D\) of order \(n\) with no isolated vertices. In this paper, we determine the values of \(\gamma^+(D) + \gamma^-(D)\) for rooted trees and connected contrafunctional digraphs \(D\), based on which we show that \(\gamma^+(D) + \gamma^-(D) \leq \frac{(2k+2)n}{2k+1}\) for every digraph \(D\) of order \(n\) with minimum out-degree or in-degree no less than \(1\), where \(2k + 1\) is the length of a shortest odd directed cycle in \(D\). Our result partially improves the result of Chartrand et al. In particular, if \(D\) contains no odd directed cycles, then \(\gamma^+(D) + \gamma^-(D) \leq n\).

Given graphs \(G\) and \(H\), an \(H\)-decomposition of \(G\) is a partition of the edge set of \(G\) such that each part is either a single edge or forms a graph isomorphic to \(H\). Let \(\gamma_H(n)\) denote the smallest number \(k\) such that any graph \(G\) of order \(n\) admits an \(H\)-decomposition with at most \(k\) parts. Here, we study the case when \(H = C_7\), the cycle of length \(7\), and prove that \(\gamma_{C_7}(n) = \left\lceil \frac{nZ^2}{4} \right\rceil\) for all \(n \geq 10\).

Given a (directed) graph \(G = (V, A)\), a subset \(X\) of \(V\) is an interval of \(G\) provided that for any \(a, b \in X\) and \(x \in V – X\), \((a, x) \in A\) if and only if \((b, x) \in A\) and \((x, a) \in A\)if and only if \((x, b) \in A\). For example, \(\emptyset\), \(\{x\}\) (\(z \in V\)), and \(V\) are intervals of \(G\), called trivial intervals. A graph, all of whose intervals are trivial, is indecomposable; otherwise, it is decomposable. A vertex \(x\) of an indecomposable graph is critical if \(G – x\) is decomposable. In 1998, J.H. Schmerl and W.T. Trotter characterized the indecomposable graphs, all of whose vertices are critical, called critical graphs. In this article, we characterize the indecomposable graphs that admit a single non-critical vertex, which we term (-1)-critical graphs, answering a question posed by Y. Boudabbous and P. Ille in a recent article studying critical vertices in indecomposable graphs.

Let \(G\) be a graph with minimum degree \(\delta(G)\). R.P. Gupta proved two interesting results: 1) A bipartite graph \(G\) has a 5-edge-coloring in which all 6 colors appear at each vertex. 2) If \(G\) is a simple graph with \(\delta(G) > 1\), then \(G\) has a \((\delta – 1)\)-edge-coloring in which all \((\delta – 1)\) colors appear at each vertex. Let \(t\) be a positive integer. In this paper, we extend the first result by showing that for every bipartite graph, there exists a \(t\)-edge coloring such that at each vertex \(v\), \(\min\{t, d(v)\}\) colors appear. Additionally, we demonstrate that if \(G\) is a graph, then the edges of \(G\) can be colored using \(t\) colors, where for each vertex \(v\), the number of colors appearing at \(v\) is at least \(\min\{t, d(v) – 1\}\), generalizing the second result.