Let \(K_v\) be a complete graph with \(v\) vertices, and \(G = (V(G), E(G))\) be a finite simple graph. A \(G\)-design \(G-GD_\lambda(v)\) is a pair \((X, \mathcal{B})\), where \(X\) is the vertex set of \(K_v\), and \(\mathcal{B}\) is a collection of subgraphs of \(K_v\), called blocks, such that each block is isomorphic to \(G\) and any two distinct vertices in \(K_v\) are joined in exactly \(\lambda\) blocks of \(\mathcal{B}\). In this paper, the existence of graph designs \(G-GD_\lambda(v)\), \(\lambda > 1\), for eight graphs \(G\) with six vertices and eight edges is completely solved.
A \({weighted \;graph}\) is one in which every edge \(e\) is assigned a nonnegative number \(w(e)\), called the \({weight}\) of \(e\). The \({weight\; of \;a \;cycle}\) is defined as the sum of the weights of its edges. The \({weighted \;degree}\) of a vertex is the sum of the weights of the edges incident with it. In this paper, motivated by a recent result of Fujisawa, we prove that a \(2\)-connected weighted graph \(G\) contains either a Hamilton cycle or a cycle of weight at least \(2m/3\) if it satisfies the following conditions:
\((1)\) The weighted degree sum of every three pairwise nonadjacent vertices is at least \(m\);\((2)\)In each induced claw and each induced modified claw of \(G\), all edges have the same weight.This extends a theorem of Zhang, Broersma and Li.
The \({restricted edge-connectivity}\) of a graph is an important parameter to measure fault-tolerance of interconnection networks. This paper determines that the restricted edge-connectivity of the de Bruijn digraph \(B(d,n)\) is equal to \(2d – 2\) for \(d \geq 2\) and \(n \geq 2\) except \(B(2,2)\). As consequences, the super edge-connectedness of \(B(d,n)\) is obtained immediately.
An edge coloring of a graph is called \({square-free}\) if the sequence of colors on certain walks is not a square, that is not of the form \(x_1, \ldots, x_m, x_{1}, \ldots, x_m\) for any \(m \in \mathbb{N}\). Recently, various classes of walks have been suggested to be considered in the above definition. We construct graphs, for which the minimum number of colors needed for a square-free coloring is different if the considered set of walks vary, solving a problem posed by Brešar and Klavžar. We also prove the following: if an edge coloring of \(G\) is not square-free (even in the most general sense), then the length of the shortest square walk is at most \(8|E(G)|^2\). Hence, the necessary number of colors for a square-free coloring is algorithmically computable.
If \(x\) is a vertex of a digraph \(D\), then we denote by \(d^+ (x)\) and \(d^- (x)\) the outdegree and the indegree of \(x\), respectively. The global irregularity of a digraph \(D\) is defined by \(i_g(D) = \max\{d^+ (x),d^- (x)\} – \min\{d^+ (y), d^- (y)\}\) over all vertices \(x\) and \(y\) of \(D\) (including \(x = y\)).
A \(c\)-partite tournament is an orientation of a complete \(c\)-partite graph. Recently, Volkmann and Winzen \([9]\) proved that \(c\)-partite tournaments with \(i_g(D) = 1\) and \(c \geq 3\) or \(i_g(D) = 2\) and \(c \geq 5\) contain a Hamiltonian path. Furthermore, they showed that these bounds are best possible.
Now, it is a natural question to generalize this problem by asking for the minimal value \(g(i,k)\) with \(i,k \geq 1\) arbitrary such that all \(c\)-partite tournaments \(D\) with \(i_g(D) \leq i\) and \(c \geq g(i,k)\) have a path covering number \(pc(D) \leq k\). In this paper, we will prove that \(4i-4k \leq g(i,k) \leq 4i-3k-1\), when \(i \geq k+2\). Especially in the case \(k = 1\), this yields that \(g(i, 1) = 4i-4\), which means that all \(c\)-partite tournaments \(D\) with the global irregularity \(i_g(D) = i\) and \(c \geq 4i-4\) contain a Hamiltonian path.
In this paper, we discuss a problem on packing a unit cube with smaller cubes, which is a generalization of one of Erdős’ favorite problems: the square-packing problem. We first give the definition of the packing function \(f_3(n)\), then give the bounds for \(f_3(n)\).
A set \(S\) of vertices in a graph \(G = (V, E)\) is a restrained dominating set of \(G\) if every vertex not in \(S\) is adjacent to a vertex in \(S\) and to a vertex in \(V \setminus S\). The graph \(G\) is called restrained domination excellent if every vertex belongs to some minimum restrained dominating set of \(G\). We provide a characterization of restrained domination excellent trees.
In this paper, \(q\)-analogues of the Pascal matrix and the symmetric Pascal matrix are studied. It is shown that the \(q\)-Pascal matrix \(\mathcal{P}_n\) can be factorized by special matrices and the symmetric \(q\)-Pascal matrix \(\mathcal{Q}_n\) has the LDU-factorization and the Cholesky factorization. As byproducts, some \(q\)-binomial identities are produced by linear algebra. Furthermore, these matrices are generalized in one or two variables, where a short formula for all powers of \(q\)-Pascal functional matrix \(\mathcal{P}_n[x]\) is given. Finally, it is similar to Pascal functional matrix, we have the exponential form for \(q\)-Pascal functional matrix.
We view a lobster in this paper as below. A lobster with diameter at least five has a unique path \(H = x_0, x_1, \ldots, x_m\) with the property that, besides the adjacencies in \(H\), both \(x_0\) and \(x_m\) are adjacent to the centers of at least one \(K_{i,s}\), where \(s > 0\), and each \(x_i\), \(1 \leq i \leq m-1\), is at most adjacent to the centers of some \(K_{1,s}\), where \(s \geq 0\). This unique path \(H\) is called the central path of the lobster. We call \(K_{1,s}\) an even branch if \(s\) is nonzero even, an odd branch if \(s\) is odd, and a pendant branch if \(s = 0\). In this paper, we give graceful labelings to some new classes of lobsters with diameter at least five. In these lobsters, the degree of each vertex \(x_i\), \(0 \leq i \leq m-1\), is even and the degree of \(x_m\) may be odd or even, and we have one of the following features:
In this paper, an algorithm for constructing self-centered graphs from trees and two more algorithms for constructing self-centered graphs from a given connected graph \(G\), by adding edges are discussed. Motivated by this, a new graph theoretic parameter \(sc_r(G)\), the minimum number of edges added to form a self-centered graph from \(G\) is defined. Bounds for this parameter are obtained and exact values of this parameter for several classes of graphs are also obtained.
A \((k;g)\)-graph is a \(k\)-regular graph with girth \(g\). A \((k;g)\)-cage is a \((k;g)\)-graph with the least number of vertices. In this note, we show that a \((k;g)\)-cage has an \(r\)-factor of girth at least \(g\) containing or avoiding a given edge for all \(r\), \(1 \leq r \leq k-1\).
This paper deals with the problem of constructing Hamiltonian paths of optimal weights in Halin graphs. There are three versions of the Hamiltonian path: none or one or two of end-vertices are specified. We present \(O(|V|)\) algorithms for all the versions of the problem.
It is widely recognized that certain graph-theoretic extremal questions play a major role in the study of communication network vulnerability. These extremal problems are special cases of questions concerning the realizability of graph invariants. We define a CS\((p, q, \lambda, \delta)\) graph as a connected, separable graph having \(p\) points, \(q\) lines, line connectivity \(\lambda\) and minimum degree \(\delta\). In this notation, if the “CS” is omitted the graph is not necessarily connected and separable. An arbitrary quadruple of integers \((a, b, c, d)\) is called CS\((p, q, \lambda, \delta)\) realizable if there is a CS\((p, q, \lambda, \delta)\) graph with \(p = a\), \(q = b\), \(\lambda = c\) and \(\delta = d\). Necessary and sufficient conditions for a quadruple to be CS\((p, q, \lambda, \delta)\) realizable are derived. In recent papers, the author gave necessary and sufficient conditions for \((p, q, \kappa, \Delta)\), \((p, q, \lambda,\Delta )\), \((p, q, \delta, \Delta)\), \((p, q, \lambda, \delta)\) and \((p, q, \kappa, \delta)\) realizability, where \(\Delta\) denotes the maximum degree for all points in a graph and \(\kappa\) denotes the point connectivity of a graph. Boesch and Suffel gave the solutions for \((p, q, \kappa)\), \((p, q, \lambda)\), \((p, q, \delta)\), \((p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability in earlier manuscripts.
An incidence graph of a given graph \(G\), denoted by \(I(G)\), has its own vertex set \(V(I(G)) = \{(ve) | v \in V(G), e \in E(G) \text{ and } v \text{ is incident to } e \text{ in } G\}\) such that the pair \(((ue)(vf))\) of vertices \((ue) (vf) \in V(I(G))\) is an edge of \(I(G)\) if and only if there exists at least one case of \(u = v, e = f, uv = e\) or \(uv = f\). In this paper, we carry out a constructive definition on incidence graphs, and investigate some properties of incidence graphs and some edge-colorings on several classes of them.
The maximum possible toughness among graphs with \(n\) vertices and \(m\) edges is considered for \(m \geq \lceil n^2/4 \rceil\). We thus extend results known for \(m \geq n\lfloor n/3 \rfloor\). When \(n\) is even, all of the values are determined. When \(n\) is odd, some values are determined, and the difficulties are discussed, leaving open questions.
In this paper, we, by means of Rosa’s \(\alpha\)-labelling and \(k\)-graceful labelling, prove that generalized spiders, generalized caterpillars, and generalized path-block chains are graceful under some conditions. Some of the results are stronger than that obtained in \([4]\).
We study convexity with respect to a definition of fractional independence in a graph \(G\) that is quantified over neighbourhoods rather than edges. The graphs that admit a so-called universal maximal fractional independent set are characterized, as are all such sets. A characterization is given of the maximal fractional independent sets which cannot be obtained as a proper convex combination of two other such sets.
In this paper, we consider the relationship between the toughness and the existence of fractional \(f\)-factors. It is proved that a graph $G$ has a fractional \(f\)-factor if \(t(G) \geq \frac{b^2+b}{a}-\frac{b+1}{b}\). Furthermore, we show that the result is best possible in some sense.
It is always fascinating to see what results when seemingly different areas of mathematics overlap. This article reveals one such result; number theory and linear algebra are intertwined to yield complex factorizations of the classic Fibonacci, Pell, Jacobsthal, and Mersenne numbers. Also, in this paper we define a new matrix generalization of the Fibonacci numbers, and using essentially a matrix approach we show some properties of this matrix sequence.
The notion of meandric polygons is introduced in this paper. A bijection exists between the set of meandric polygons and that of closed meanders. We use these polygons to enumerate the set of meanders which have a fixed number of arcs of the meandric curves lying above and below the horizontal line at a given point.
In this paper, we give a sufficient and necessary condition for a \(k\)-extendable graph to be \(2k\)-factor-critical when \(k = \frac{v}{4}\), and prove some results on independence numbers in \(n\)-factor-critical graphs and \(k\frac{1}{2}\)-extendable graphs.
In this paper, we show that some families of graphs are arbitrarily graceful or almost graceful.
We consider the lattice of order ideals of the union of an \(n\)-element fence and an antichain of size \(i\), whose Hasse diagram turns out to be isomorphic to the \(i\)-th extended Fibonacci cube. We prove that the Whitney numbers of these lattices form a unimodal sequence satisfying a particular property, called \({alternating}\), we find the maximum level of the game sequence and determine the exact values of these numbers.
Let \(D\) be a strongly connected digraph with order at least two. Let \(T(D)\) denote the total digraph of \(D\), and let \(\kappa(D)\) and \(\lambda(D)\) denote the connectivity and arc-connectivity of \(D\), respectively. In this paper, we study super-arc-connected and super-connected total digraphs. The following results are obtained:
A vertex\(|\)matching-partition \((V|M)\) of a simple graph \(G\) is a spanning collection of vertices and independent edges of \(G\). Let vertex \(v \in V\) have weight \(w_v\) and edge \(e \in M\) have weight \(w_e\). Then the weight of \(V|M\) is \(w(V|M) = \prod_{v \in V} w_v + \prod_{e \in M} w_e\). Define the vertex|matching-partition function of \(G\) as \(W(G) = \sum_{V|M} w(V|M)\).
In this paper, we study this function when \(G\) is a path and a cycle. We generate all orthogonal polynomials as vertex|matching-partition functions of suitably labelled paths, and indicate how to find their derivatives in some cases. Here Taylor’s Expansion is used, and an application to associated polynomials is given. We also give a combinatorial interpretation of coefficients in the case of multiplicative and additive weights. Results are extended to the weighted cycle.
Let \(k\) be a nonnegative integer, and let \(\gamma(G)\) and \(i(G)\) denote the domination number and the independent domination number of a graph \(G\), respectively. The so-called \(i_k\)-perfect graphs consist of all such graphs \(G\) in which \(i(H) – \gamma(H) \leq k\) holds for every induced subgraph \(H\) of \(G\). This concept, introduced by I. Zverovich in \([5]\), generalizes the well-known domination perfect graphs. He conjectured that \(i\gamma (k)\)-perfect graphs also have a finite forbidden induced subgraphs characterization, as is the case for domination perfect graphs. Recently, Dohmen, Rautenbach, and Volkmann obtained such a characterization for all \(i\gamma(1)\)-perfect forests. In this paper, we characterize the \(i\gamma(1)\)-perfect graphs with girth at least six.
Let \(G\) be a simple and connected graph of order \(p \geq 2\). A \({proper k-total-coloring}\) of a graph \(G\) is a mapping \(f\) from \(V(G) \bigcup E(G)\) into \(\{1, 2, \ldots, k\}\) such that every two adjacent or incident elements of \(V(G) \bigcup E(G)\) are assigned different colors. Let \(C_f(u) = f(u) \bigcup \{f(uv) | uv \in E(G)\}\) be the \({neighbor \;color-set}\) of \(u\). If \(C_f(u) \neq C_f(v)\) for any two vertices \(u\) and \(v\) of \(V(G)\), we say \(f\) is a \({vertex-distinguishing \;proper\; k-total-coloring}\) of \(G\), or a \({k-VDT-coloring}\) of \(G\) for short. The minimal number of all \(k\)-VDT-colorings of \(G\) is denoted by \(\chi_{vt}(G)\), and it is called the \({VDTC \;chromatic \;number}\) of \(G\). For some special families of graphs, such as the complete graph \(K_n\), complete bipartite graph \(K_{m,n}\), path \(P_m\), and circle \(C_m\), etc., we determine their VDTC chromatic numbers and propose a conjecture in this article.
The cochromatic number of a graph \(G\), denoted by \(z(G)\), is the fewest number of parts we need to partition \(V(G)\) so that each part induces in \(G\) an empty or a complete graph. A graph \(G\) with \(z(G) = n\) is called \({critically n-cochromatic}\) if \(z(G – v) = n – 1\) for each vertex \(v\) of \(G\), and \({minimally n-cochromatic}\) if \(z(G – e) = n – 1\) for each edge \(e\) of \(G\).
We show that for a graph \(G\), \(K_{1} \cup G \cup K_{2} \cup \cdots \cup K_{n-1} \cup G\) is a critically \(n\)-cochromatic graph if and only if \(G\) is \(K_{n}\), \((n \geq 2)\). We consider general minimally cochromatic graphs and obtain a result that a minimally cochromatic graph is either a critically cochromatic graph or a critically cochromatic graph plus some isolated vertices. We also prove that given a graph \(G\), then \(K_{1} \cup G \cup K_{2} \cup \cdots \cup K_{n-1} \cup G\) \((n \geq 2)\) is minimally \(n\)-cochromatic if and only if \(G\) is \(K_{n}\) or \(\overline{K_{n-1}} \cup \overline{K_{p}}\) for \(p \geq 1\). We close by giving some properties of minimally \(n\)-cochromatic graphs.
We examine the inverse domination number of a graph, as well as two reasonable candidates for the fractional analogue of this parameter. We also examine the relations among these and other graph parameters. In particular, we show that both proposed fractional analogues of the inverse domination number are no greater than the fractional independence number. These results establish the fractional analogue of a well-known conjecture about the inverse domination and vertex independence numbers of a graph.
We consider a \(2\)-coloring of arcs on the primitive extremal tournament with the largest exponent on \(n\) vertices and \(m\) arcs. This \(2\)-colored digraph is a \(2\)-primitive tournament. Then we consider the \(2\)-exponent of a \(2\)-primitive tournament. In this paper, we give an upper bound for the \(2\)-exponent of the primitive extremal tournament.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.