The Fibonacci graph \( G_n \) is the graph whose vertex set is the collection of \( n \)-bit binary strings having no contiguous ones, and two vertices are adjacent if and only if their Hamming distance is one. Values of several graphical invariants are determined for these graphs, and bounds are found for other invariants.

Given a configuration of pebbles on the vertices of a connected graph \( G \), a \emph{pebbling move} is defined as the removal of two pebbles from some vertex and the placement of one of these on an adjacent vertex. We introduce the notion of domination cover pebbling, obtained by combining graph cover pebbling with the theory of domination in graphs. The domination cover pebbling number, \( \psi(G) \), of a graph \( G \) is the minimum number of pebbles that are placed on \( V(G) \) such that after a sequence of pebbling moves, the set of vertices with pebbles forms a dominating set of \( G \), regardless of the initial configuration of pebbles. We discuss basic results and determine \( \psi(G) \) for paths, cycles, and complete binary trees.

We show that the double domination number of an \( n \)-vertex, isolate-free graph with minimum degree \( \delta \) is bounded above by

\[\frac{n(\ln(\delta + 1) + \ln \delta + 1)}{\delta}.\]

This result improves a previous bound obtained by J. Harant and M. A. Henning [On double domination in graphs, \emph{Discuss. Math. Graph Theory} \textbf{25} (2005), 29-34]. Further, we show that for fixed \( k \) and large \( \delta \), the \( k \)-tuple domination number is at most

\[\frac{n(\ln \delta + (k – 1 + o(1))\ln \ln \delta)}{\delta},\]

a bound that is essentially best possible.

Let \(\alpha\)-resolvable STS(\(v\)) denote a Steiner triple system of order \(v\) whose blocks are partitioned into classes such that each point of the design occurs in precisely \(\alpha\) blocks in each class. We show that for \(v \equiv u \equiv 1 \pmod{6}\) and \(v \geq 3u + 4\), there exists an \(\alpha\)-resolvable STS(\(v\)) containing an \(\alpha\)-resolvable sub-STS(\(u\)) for all suitable \(\alpha\).

A vertex set \( S \subseteq V(G) \) of a graph \( G \) is a \( 2 \)-dominating set of \( G \) if \( |N(v) \cap S| \geq 2 \) for every vertex \( v \in (V(G) – S) \), where \( N(v) \) is the neighborhood of \( v \). The \( 2 \)-domination number \( \gamma_2(G) \) of graph \( G \) is the minimum cardinality among the \( 2 \)-dominating sets of \( G \). In this paper, we present the following Nordhaus-Gaddum-type result for the \( 2 \)-domination number. If \( G \) is a graph of order \( n \), and \( \bar{G} \) is the complement of \( G \), then

$$ \gamma_2(G) + \gamma_2(\bar{G}) \leq n + 2, $$

and this bound is best possible in some sense.

The Graph Isomorphism (GI) problem asks if two graphs are isomorphic. Algorithms which solve GI have applications in, but not limited to, SAT solver engines, isomorph-free generation, combinatorial analysis, and analyzing chemical structures. However, no algorithm has been found which solves GI in polynomial time, implying that hard instances should exist. One of the most popular algorithms, implemented in the software package nauty, canonically labels a graph and outputs generators for its automorphism group. In this paper, we present some methods that improve its performance on graphs that are known to pose difficulty.

Let \( C \) be the set of distinct ways in which the vertices of a \( 5 \)-cycle may be coloured with at most two colours, called \emph{colouring types}, and let \( S \subseteq C \). Suppose we colour the vertices of \( K_v \) with at most two colours. If \( \mathcal{D} \) is a \( 5 \)-cycle decomposition of \( K_v \), such that the colouring type of each \( 5 \)-cycle is in \( S \), and every colouring type in \( S \) is represented in \( \mathcal{D} \), then \( \mathcal{D} \) is said to have a \emph{proper colouring type} \( S \). For all \( S \) with \( |S| \leq 2 \), we determine some necessary conditions for the existence of a \( 5 \)-cycle decomposition of \( K_v \) with proper colouring type \( S \). In many cases, we show that these conditions are also sufficient.

Most computer algebra packages for Weyl groups use generators and relations and the Weyl group elements are expressed as reduced words in the generators. This representation is not unique and leads to computational problems. In [HHR06], the authors introduce the representation of Weyl group elements uniquely as signed permutations. This representation is useful for the study of symmetric spaces and their representations.

A computer algebra package enabling one to do computations related to symmetric spaces would be an important tool for researchers in many areas of mathematics, including representation theory, Harish Chandra modules, singularity theory, differential and algebraic geometry, mathematical physics, character sheaves, Lie theory, etc. In this paper, we use the representation of Weyl group elements as signed permutations to improve the algorithms of [DH05]. These algorithms compute the fine structure of symmetric spaces and nice bases for local symmetric spaces.

A vertex subset \( X \) of a simple graph is called OC-irredundant (respectively CO-irredundant) if for each \( v \in X \), \( N(v) – N[X – \{v\}] \neq \emptyset \) (respectively \( N[v] – N(X – \{v\}) \neq \emptyset \)). Sharp bounds involving order and maximum degree for the minimum cardinality of a maximal OC-irredundant set and a maximal CO-irredundant set of a tree are obtained, and extremal trees are exhibited.

For any \( k \in \mathds{N} \), a graph \( G = (V, E) \) is said to be \( \mathds{Z}_k \)-magic if there exists a labeling \( l: E(G) \to \mathds{Z}_k – \{0\} \) such that the induced vertex set labeling \( l^+: V(G) \to \mathds{Z}_k \), defined by

$$ l^+(v) = \sum_{uv \in E(G)} l(uv) $$

is a constant map. For a given graph \( G \), the set of all \( k \in \mathds{N} \) for which \( G \) is \( \mathds{Z}_k \)-magic is called the integer-magic spectrum of \( G \) and is denoted by \( IM(G) \). In this paper, we will consider the functional extensions of \( P_n \) (\( n = 2, 3, 4 \)) and will determine their integer-magic spectra.

Let \( G(V, E) \) be a weighted connected simple graph. Given a pair of vertices \( u, v \in V \), let \( Max(u, v) \) denote the maximum average path value over all simple paths from \( u \) to \( v \). For a given simple path from \( u \) to \( v \), the average path value, \( apv_P(u, v) = \frac{min(P)}{length(P)} \), where \( min(P) \) is the weight of the minimum weight edge in the path \( P \) and \( length(P) \) is the number of edges in \( P \). This notion of average path value has been used in the analysis of social networks. Algorithms are presented for the calculation of \emph{average path value}.

For the purpose of large scale computing, we are interested in linking computers into large interconnection networks. In order for these networks to be useful, the underlying graph must possess desirable properties such as a large number of vertices, high connectivity, and small diameter. In this paper, we are interested in the alternating group graph, as an interconnection network, and the \( k \)-Disjoint Path Problem. In 2005, Cheng, Kikas, and Kruk showed that the alternating group graph, \( AG_n \), has the \( (n – 2) \)-Disjoint Path Property. However, their proof was an existence proof only; they did not show how to actually construct the \( (n – 2) \) disjoint paths. In 2006, Boats, Kikas, and Oleksik developed an algorithm for constructing three disjoint paths in the graph \( AG_5 \). Their algorithm exploited the hierarchical structure of \( AG_n \) to construct the paths. In this paper, we develop a purely algebraic algorithm that constructs the \( (n – 2) \) disjoint paths from scratch. This algebraic approach can be used for other Cayley graphs such as the split-star and the star graphs. Indeed, we believe that our approach can be used for any Cayley graph. We close with remarks on possible research directions stemming from this work.

The computation of the maximum toughness among graphs with \( n \) vertices and \( m \) edges is considered for \( \lceil{5n}/{2}\rceil \leq m < 3n \). We show that there are only finitely many cases in which the toughness value \( \frac{5}{2} \) cannot be achieved. This is in stark contrast with the known result that there is a \( \frac{3}{2} \)-tough graph on \( n \) vertices and \( \lceil{3n}/{2}\rceil \) edges if and only if \( n \equiv 0, 5 \pmod{6} \). However, constructions related to those used in the cubic case are also employed here. Our constructions additionally provide an infinite family of graphs that are supertough and not \( K_{1,3} \)-free.

A simple graphoidal cover of a graph \( G \) is a collection \( \psi \) of (not necessarily open) paths in \( G \) such that every path in \( \psi \) has at least two vertices, every vertex of \( G \) is an internal vertex of at most one path in \( \psi \), every edge of \( G \) is in exactly one path in \( \psi \), and any two paths in \( \psi \) have at most one vertex in common. The minimum cardinality of a simple graphoidal cover of \( G \) is called the simple graphoidal covering number of \( G \) and is denoted by \( \eta_s(G) \). In this paper, we determine the value of \( \eta_s \) for several families of graphs. We also obtain several bounds for \( \eta_s \) and characterize graphs attaining the bounds.

In this paper, we discuss how the addition of a new edge affects the irregularity strength of a graph.

Let \( G \) be a graph of size \( n \) with vertex set \( V(G) \) and edge set \( E(G) \). A \( \sigma \)-labeling of \( G \) is a one-to-one function \( f: V(G) \to \{0, 1, \dots, 2n\} \) such that \( \{|f(u) – f(v)| : \{u, v\} \in E(G)\} = \{1, 2, \dots, n\} \). Such a labeling of \( G \) yields cyclic \( G \)-decompositions of \( K_{2n+1} \) and of \( K_{2n+2} – F \), where \( F \) is a \( 1 \)-factor of \( K_{2n+2} \). It is conjectured that a \( 2 \)-regular graph of size \( n \) has a \( \sigma \)-labeling if and only if \( n \equiv 0 \) or \( 3 \pmod{4} \). We show that this conjecture holds when the graph has at most three components.

The Kneser graph \( K(m, n) \) (when \( m > 2n \)) has the \( n \)-subsets of an \( m \)-set as its vertices, two vertices being adjacent in \( K(m, n) \) whenever they are disjoint sets. The \( k \)th-chromatic number of any graph \( G \) (denoted by \( \chi_k(G) \)) is the least integer \( t \) such that the vertices can be assigned \( k \)-subsets of \( \{1, 2, \dots, t\} \) with adjacent vertices receiving disjoint \( k \)-sets. S. Stahl has conjectured that, if \( k = qn – r \) where \( q \geq 1 \) and \( 0 \leq r < n \), then \( \chi_k(K(m, n)) = qm – 2r \). This expression is easily verified when \( r = 0 \); Stahl has also established its validity for \( q = 1 \), for \( m = 2n + 1 \) and for \( k = 2, 3 \). We show here that the expression is also valid for all \( q \geq 2 \) in the following further classes of cases: \begin{enumerate}[label=(\roman*)] \item \( 2n + 1 < m \leq n(2 + r^{-1}) \) (\( 0 < r 1 \));
\item \( 4 \leq n \leq 6 \) and \( 1 \leq r \leq 2 \) (all \( m \));
\item \( 7 \leq n \leq 11 \) and \( r = 1 \) (all \( m \));
\item \( (n, r, m) = (7, 2, 18), (12, 1, 37), (12, 1, 38) \) or \( (13, 1, 40) \).
\end{enumerate}

We prove that for a finite planar space \( S = (\mathcal{P}, \mathcal{L}, \mathcal{H}) \) with no disjoint planes and with a constant number of planes on a line, the number \( \ell \) of lines is greater than or equal to the number \( c \) of planes, and the equality holds true if and only if \( S \) is either the finite Desarguesian 4-dimensional projective space \( PG(4,q) \), or the complete graph \( K_5 \).

A \((p, q)\)-graph \( G \) is said to be \textbf{edge graceful} if the edges can be labeled by \( 1, 2, \ldots, q \) so that the vertex sums are distinct, mod \( p \). It is shown that if a tree \( T \) is edge-graceful, then its order must be odd. Lee conjectured that all trees of odd orders are edge-graceful. J. Mitchem and A. Simoson introduced the concept of super edge-graceful graphs, which is a stronger concept than edge-graceful for some classes of graphs.

A graph \( G = (V, E) \) of order \( p \) and size \( q \) is said to be \textbf{super edge-graceful} (SEG) if there exists a bijection
\[
\text{f: E} \to
\begin{cases}
\{0, +1, -1, +2, -2, \ldots, \frac{q-1}{2}, -\frac{q-1}{2}\} & \text{if } q \text{ is odd} \\
\{+1, -1, +2, -2, \ldots, \frac{q}{2}, -\frac{q}{2}\} & \text{if } q \text{ is even}
\end{cases}
\]
such that the induced vertex labeling \( f^* \) defined by \( f^*(u) = \sum \{ f(u, v) : (u, v) \in E \} \) has the property:
\[
f^*: V \to
\begin{cases}
\{0, +1, -1, \ldots, +\frac{p-1}{2}, -\frac{p-1}{2}\} & \text{if } p \text{ is odd} \\
\{+1, -1, \ldots, +\frac{p}{2}, -\frac{p}{2}\} & \text{if } p \text{ is even}
\end{cases}
\]
is a bijection.

The conjecture is still unsettled. In this paper, we first characterize spiders of even orders which are not SEG. We then exhibit some spiders of even orders which are SEG of diameter at most four. By the concepts of the irreducible part of an even tree \( T \), we show that an infinite number of spiders of even orders are SEG. Finally, we provide some conjectures for further research.

In this paper, we shall consider acquisition sequences of a graph. The formation of each acquisition sequence is a process that creates an independent set. Each acquisition sequence is a sequence of “acquisitions” which are defined on a graph \( G \) for which each vertex originally has a value of one associated with it. In an acquisition, a vertex transfers all of its value to an adjacent vertex with equal or greater value. For an acquisition sequence, one continues until no more acquisitions are possible. The parameter \( a(G) \) is defined to be the minimum possible number of vertices with a nonzero value at the conclusion of such an acquisition sequence. Clearly, if \( S \) is a set of vertices with nonzero values at the end of some acquisition sequence, then \( S \) is independent, and we call such a set \( S \) an acquisition set. We show that for a given graph \( G \), “Is \( a(G) = 1 \)” is NP-complete, and describe a linear time algorithm to determine the acquisition number of a caterpillar.