Suppose that \(D\) is an acyclic orientation of a graph \(G\). An arc of \(D\) is called dependent if its reversal creates a directed cycle. Let \(d_{\min}(G)\) (\(d_{\max}(G)\)) denote the minimum (maximum) of the number of dependent arcs over all acyclic orientations of \(G\). We call \(G\) fully orientable if \(G\) has an acyclic orientation with exactly \(d\) dependent arcs for every \(d\) satisfying \(d_{\min}(G) \leq d \leq d_{\max}(G)\). A graph \(G\) is called chordal if every cycle in \(G\) of length at least four has a chord. We show that all chordal graphs are fully orientable.

A graph \(G\) with no isolated vertex is total restrained domination vertex critical if for any vertex \(v\) of \(G\) that is not adjacent to a vertex of degree one, the total restrained domination number of \(G – v\) is less than the total restrained domination number of \(G\). We call these graphs \(\gamma_{tr}\)-vertex critical. If such a graph \(G\) has total restrained domination number \(k\), then we call it \(k\)-\(\gamma_{tr}\)-vertex critical. In this paper, we study some properties in \(\gamma_{tr}\)-vertex critical graphs of minimum degree at least two.

In this paper, we give a necessary and sufficient condition for a function with the form \(tr(\sum_{i=1}^q a_ix^{i(q-1)})\) to be a generalized bent function. We indicate that these generalized bent functions are just those which could be constructed from partial spreads. We also introduce a method to calculate these generalized bent functions by means of interpolation.

Let \(G\) be a finite group and \(n\) a positive integer. The \(n\)-th commutativity degree \(P_n(G)\) of \(G\) is the probability that the \(n\)-th power of a random element of \(G\) commutes with another random element of \(G\). In 1968, P. Erdős and P. Turán investigated the case \(n = 1\), involving only methods of combinatorics. Later, several authors improved their studies and there is a growing literature on the topic in the last 10 years. We introduce the relative \(n\)-th commutativity degree \(P_n(H,G)\) of a subgroup \(H\) of \(G\). This is the probability that an \(n\)-th power of a random element in \(H\) commutes with an element in \(G\). The influence of \(P_n(G)\) and \(P_n(H,G)\) on the structure of \(G\) is the purpose of the present work.

It is known that determining the Lagrangian of a general \(r\)-uniform hypergraph is useful in practice and is non-trivial when \(r \geq 3\). In this paper, we explore the Lagrangians of \(3\)-uniform hypergraphs with edge sets having restricted structures. In particular, we establish a number of optimization problems for finding the largest Lagrangian of \(3\)-uniform hypergraphs with the number of edges \(m = \binom{k}{3} – a\), where \(a = 3\) or \(4\). We also verify that the largest Lagrangian has the colex ordering structure for \(3\)-uniform hypergraphs when the number of edges is small.

Let \(D\) be an acyclic orientation of a simple graph \(G\). An arc of \(D\) is called dependent if its reversal creates a directed cycle. Let \(d(D)\) denote the number of dependent arcs in \(D\). Define \(d_{\min}(G)\) (\(d_{\max}(G)\)) to be the minimum (maximum) number of \(d(D)\) over all acyclic orientations \(D\) of \(G\). We call \(G\) fully orientable if \(G\) has an acyclic orientation with exactly \(k\) dependent arcs for every \(k\) satisfying \(d_{\min}(G) \leq k \leq d_{\max}(G)\). In this paper, we prove that the square of a cycle \(C_n\) is fully orientable except for \(n = 6\).

Let \(G = (V, A)\) be a graph. For every subset \(X\) of \(V\), the sub-graph \(G(X) = (X, A \cap (X \times X))\) of \(G\) induced by \(X\) is associated. The dual of \(G\) is the graph \(G^* = (V, A^*)\)such that \(A^* = \{(x,y): (y,x) \in A\}\). A graph \(G’\) is hemimorphic to \(G\) if it is isomorphic to \(G\) or \(G^*\). Let \(k \geq 1\) be an integer. A graph \(G’\) defined on the same vertex set \(V\) of \(G\) is \((\leq k)\)-hypomorphic (resp. \((\leq k)\)-hemimorphic) to \(G\) if for all subsets \(X\) of \(V\) with at most \(k\) elements, the sub-graphs \(G(X)\) and \(G'(X)\) are isomorphic (resp. hemimorphic). \(G\) is called \((\leq k)\)-reconstructible (resp. \((\leq k)\)-half-reconstructible) provided that every graph \(G’\) which is \((\leq k)\)-hypomorphic (resp. \((\leq k)\)-hemimorphic) to \(G\) is hypomorphic (resp. hemimorphic) to \(G\). In 1972, G. Lopez {14,15] established that finite graphs are \((\leq 6)\)-reconstructible. For \(k \in \{3,4,5\}\), the \((<k)\)-reconstructibility problem for finite graphs was studied by Y. Boudabbous and G. Lopez [1,5]. In 2006, Y. Boudabbous and C. Delhommé [4] characterized, for each \(k \geq 4\), all \((\leq k)\)-reconstructible graphs. In 1993, J. G. Hagendorf and G. Lopez showed in [12] that finite graphs are \((\leq 12)\)-half-reconstructible. After that, in 2003, J. Dammak [8] characterized the \((\leq k)\)-half-reconstructible finite graphs for every \(7 \leq k \leq 11\). In this paper, we characterize for each integer \(7 \leq k \leq 12\), all \((\leq k)\)-half-reconstructible graphs.

In this paper, we study the relations between degree sum and extending paths in graphs. The following result is proved. Let \(G\) be a graph of order \(n\), if \(d(u)+d(v) \geq n+k\) for each pair of nonadjacent vertices \(u,v\) in \(V(G)\), then every path \(P\) of \(G\) with \(\frac{n}{k+2} \leq 2 < n\) is extendable. The bound \(\frac{n}{k+2}+2\) is sharp.

A median graph is a connected graph in which, for every three vertices, there exists a unique vertex \(m\) lying on the geodesic between any two of the given vertices. We show that the only median graphs of the direct product \(G \times H\) are formed when \(G = P_k\), for any integer \(k \geq 3\), and \(H = P_l\), for any integer \(l \geq 2\), with a loop at an end vertex, where the direct product is taken over all connected graphs \(G\) on at least three vertices or at least two vertices with at least one loop, and connected graphs \(H\) with at least one loop.

An urn contains \(m\) distinguishable balls with \(m\) distinguishable colors. Balls are drawn for \(n\) times successively at random
and with replacement from the urn. The mathematical expectation of the number of drawn colors is investigated. Some combinatorial identities on the Stirling number of the second kind \(S(n,m)\) are derived by using probabilistic method.