Consider a tree \(T = (V, E)\) with root \(r \in V\) and \(|V| = N\). Let \(p_v\) be the probability that a user wants to access node \(v\). A bookmark is an additional link from \(r\) to any other node of \(T\). We want to add \(k\) bookmarks to \(T\), so as to minimize the expected access cost from \(r\), measured by the average length of the shortest path. We present a characterization of an optimal assignment of \(k\) bookmarks in a perfect binary tree with uniform probability distribution of access and \(k \leq \sqrt{N + 1}\).

We show various combinatorial identities that are generated by tree counting arguments. In particular, we give formulas for \(n^p\) and \(\tau(K_{s,t})\) which establishes an equivalence.

The question of necessary and sufficient conditions for the existence of a simple \(3\)-uniform hypergraph with a given degree sequence is a long outstanding open question. We provide a result on degree sequences of \(3\)-hypergraphs which shows that any two \(3\)-hypergraphs with the same degree sequence can be transformed into each other using a sequence of trades, also known as null-\(3\)-hypergraphs. This result is similar to the Havel-Hakimi theorem for degree sequences of graphs.

In this paper we consider the problem as follows: Given a bipartite graph \(G = (V_1, V_2; E)\) with \(|V_1| = |V_2| = n\) and a positive integer \(k\), what degree condition is sufficient to ensure that for any \(k\) distinct vertices \(v_1, v_2, \ldots, v_k\) of \(G\), \(G\) contains \(k\) independent quadrilaterals \(Q_1, Q_2, \ldots, Q_k\) such that \(v_i \in V(Q_i)\) for every \(i \in \{1, 2, \ldots, k\}\), or \(G\) has a \(2\)-factor with \(k\) independent cycles of specified lengths with respect to \(\{v_1, v_2, \ldots, v_k\}\)? We will prove that if \(d(x) + d(y) \geq \left\lceil (4n + k)/3 \right\rceil\) for each pair of nonadjacent vertices \(x \in V_1\) and \(y \in V_2\), then, for any \(k\) distinct vertices \(v_1, v_2, \ldots, v_k\) of \(G\), \(G\) contains \(k\) independent quadrilaterals \(Q_1, Q_2, \ldots, Q_k\) such that \(v_i \in V(Q_i)\) for each \(i \in \{1, \ldots, k\}\). Moreover, \(G\) has a \(2\)-factor with \(k\) cycles with respect to \(\{v_1, v_2, \ldots, v_k\}\) such that \(k – 1\) of them are quadrilaterals. We also discuss the degree conditions in the above results.

We call the graph \(G\) an edge \(m\)-coloured if its edges are coloured with \(m\) colours. A path (or a cycle) is called monochromatic if all its edges are coloured alike. A subset \(S \subseteq V(G)\) is independent by monochromatic paths if for every pair of different vertices from \(S\) there is no monochromatic path between them. In \([5]\) it was defined the Fibonacci number of a graph to be the number of all independent sets of \(G\); recall that \(S\) is independent if no two of its vertices are adjacent. In this paper we define the concept of a monochromatic Fibonacci number of a graph which gives the total number of monochromatic independent sets of \(G\). Moreover we give the number of all independent by monochromatic paths sets of generalized lexicographic product of graphs using the concept of a monochromatic Fibonacci polynomial of a graph. These results generalize the Fibonacci number of a graph and the Fibonacci polynomial of a graph.

Let \(D = (V, E)\) be a primitive digraph. The exponent of \(D\) at a vertex \(u \in V\), denoted by \(\exp_D(u)\), is defined to be the least integer \(k\) such that there is a walk of length \(k\) from \(u\) to \(v\) for each \(v \in V\). Let \(V = \{v_1, v_2, \ldots, v_n\}\). The vertices of \(V\) can be ordered so that \(\exp_D(v_{i_1}) \leq \exp_D(v_{i_2}) \leq \ldots \leq \exp_D(v_{i_n}) = \gamma(D)\). The number \(\exp_p(v_n)\) is called the \(k\)-exponent of \(D\), denoted by \(\exp_p(k)\). We use \(L(D)\) to denote the set of distinct lengths of the cycles of \(D\). In this paper, we completely determine the \(1\)-exponent sets of primitive, minimally strong digraphs with \(n\) vertices and \(L(D) = \{p, q\}\), where \(3 \le p < q\) and \(p + q > n\).

Let \(\mathcal{C}\) be any class of finite graphs. A graph \(G\) is \(\mathcal{C}\)-ultrahomogeneous if every isomorphism between induced subgraphs belonging to \(\mathcal{C}\) extends to an automorphism of \(G\). We study finite graphs that are \({K}_*\)-ultrahomogeneous, where \({K}_*\) is the class of complete graphs. We also explicitly classify the finite graphs that are \(\sqcup{K}_{*}\)-ultrahomogeneous, where \(\sqcup{K}_{*}\) is the class of disjoint unions of complete graphs.

For any positive integer \(n\), let \(S_n\), denote the set of all permutations of the set \(\{1,2,\ldots,n\}\). We think of a permutation just as an ordered list. For any \(p\) in \(S_n\), and for any \(i \leq n\), let \(p \downarrow i\) be the permutation on the set \(\{1,2,\ldots,n – 1\}\) obtained from \(p\) as follows: delete \(i\) from \(p\) and then subtract \(1\) in place from each of the remaining entries of \(p\) which are larger than \(i\). For any \(p\) in \(S_n\), we let \(R(p) = \{q \in S_{n-1} : g = p \downarrow i \;\text{for some} \;i \leq n\}\), the set of reductions of \(p\). It is shown that, for \(n > 4\), any \(p\) in \(S_n\), is determined by its set of reductions \(R(p)\).

A connected graph is said to be super edge-connected if every minimum edge-cut isolates a vertex. The restricted edge-connectivity \(\lambda’\) of a connected graph is the minimum number of edges whose deletion results in a disconnected graph such that each connected component has at least two vertices. A graph \(G\) is called \(\lambda’\)-optimal if \(\lambda'(G) = \min\{d_G(u)+d_G(v)-2: uv \text{ is an edge in } G\}\). This paper proves that for any \(d\) and \(n\) with \(d \geq 2\) and \(n\geq 1\) the Kautz undirected graph \(UK(d, 1)\) is \(\lambda’\)-optimal except \(UK(2,1)\) and \(UK(2,2)\) and, hence, is super edge-connected except \(UK(2, 2)\).

In a \((k, d)\)-relaxed coloring game, two players, Alice and Bob, take turns coloring the vertices of a graph \(G\) with colors from a set \(C\) of \(k\) colors. A color \(c\) is legal for an uncolored vertex (at a certain step) means that after coloring \(x\) with color \(i\), the subgraph induced by vertices of color \(i\) has maximum degree at most \(d\). Each player can only color a vertex with a legal color. Alice’s goal is to have all the vertices colored, and Bob’s goal is the opposite: to have an uncolored vertex without legal color. The \(d\)-relaxed game chromatic number of a graph \(G\), denoted by \(\chi^{(d)}_g(G)\) is the least number \(k\) so that when playing the \((k,d)\)-relaxed coloring game on \(G\), Alice has a winning strategy. This paper proves that if \(G\) is an outer planar graph, then \(\chi^{(d)}_g(G) \leq 7 – d\) for \(d = 0, 1, 2, 3, 4\).