A branch vertex of a tree is a vertex of degree at least three. Matsuda, et. al. [7] conjectured that, if $n$ and $k$ are non-negative integers and $G$ is a connected claw-free graph of order $n$, there is either an independent set on $2k+3$ vertices whose degrees add up to at most $n–3$, or a spanning tree with at most $k$ branch vertices. The authors of the conjecture proved it for $k=1$; we prove it for $k=2$.

Orbit code is a class of constant dimension code which is defined as orbit of a subgroup of the general linear group $G{L}_n(\mathbb{F}q)$, acting on the set of all the subspaces of vector space ${\mathbb{F}}_q^n$. In this paper, the construction of orbit codes based on the singular general linear group $GLn+l,n({\mathbb{F}}_q)$ acting on the set of all the subspaces of type $(m,k)$ in singular linear spaces ${\mathbb{F}}_q^{n+l}$ is given. We give a characterization of orbit code constructed in singular linear space ${\mathbb{F}}_q^{n+l}$, and then give some basic properties of the constructed orbit codes. Finally, two examples about our orbit codes for understanding these properties explicitly are presented.

We use heuristic algorithms to find terraces for small groups. We show that Bailey’s Conjecture (that all groups other than the non-cyclic elementary abelian 2-groups are terraced) holds up to order 511, except possibly at orders 256 and 384. We also show that Keedwell’s Conjecture (that all non-abelian groups of order at least 10 are sequenceable) holds up to order 255, and for the groups $A_6,S_6,PSL(2,q_1)$ and $PGL(2,q_2)$ where $q_1$ and $q_2$ are prime powers with $3\le q_1\le 11$ and $3\le q_2\le 8$. A sequencing for a group of a given order implies the existence of a complete Latin square at that order. We show that there is a sequenceable group for each odd order up to 555 at which there is a non-abelian group. This gives 31 new orders at which complete Latin squares are now known to exist, the smallest of which is 63.

In addition, we consider terraces with some special properties, including constructing a directed $T_2$-terrace for the non-abelian group of order 21 and hence a Roman-2 square of order 21 (the first known such square of odd order). Finally, we report the total number of terraces and directed terraces for groups of order at most 15.

An adjacent vertex distinguishing total coloring of a graph $G$ is a proper total coloring of $G$ such that no pair of adjacent vertices are incident to the same set of colors. The minimum number of colors required for an adjacent vertex distinguishing total coloring of $G$ is denoted by $\chi {”}_a(G)$. In this paper, we prove that if $G$ is an outer 1-planar graph with at least two vertices, then $\chi {”}_a(G)\le max\{\mathrm{\Delta }+2,8\}$. Moreover, we also prove that when $\mathrm{\Delta }\ge 7$, $\chi {”}_a(G)=\mathrm{\Delta }+2$ if and only if $G$ contains two adjacent vertices of maximum degree.

In this paper, we study five methods to construct $\alpha$-trees by using vertex amalgamations of smaller $\alpha$-trees. We also study graceful and $\alpha$-labelings for graphs that are the union of $t$ copies of an $\alpha$-graph $G$ of order $m$ and size $n$ with a graph $H$ of size $t$. If $n>m$, we prove that the disjoint union of $H$ and $t$ copies of $G$ is graceful when $H$ is graceful, and that this union is an $\alpha$-graph when $H$ is any linear forest of size $t–1$. If $n=m$, we prove that this union is an $\alpha$-graph when $H$ is the path $P_{t-1}$.

For a bipartite graph $G$ and a positive integer $s$, the $s$-bipartite Ramsey number $B{R}_s(G)$ of $G$ is the minimum integer $t$ with $t\ge s$ for which every red-blue coloring of $K_{s,t}$ results in a monochromatic $G$. A formula is established for $B{R}_s(K_{r,r})$ when $s\in \{2r–1,2r\}$ when $r\ge 2$. The $s$-bipartite Ramsey numbers are studied for $K_{3,3}$ and various values of $s$. In particular, it is shown that $B{R}_5(K_{3,3})=41$ when $s\in \{5,6\}$, $B{R}_s(K_{3,3})=29$ when $s\in \{7,8\}$, and $17\le B{R}_{10}(K_{3,3})\le 23$.

Research collaboration is a central mechanism that combines distributed knowledge and expertise into common new original ideas. Considering the lists of publications of László Lovász from the Hungarian bibliographic database MTMT, we illustrate and analyze the collaboration network determined by all co-authors of Lovász, considering only their joint works with Lovász.

In the second part, we construct and analyze the co-authorship network determined by the collaborating authors of all scientific documents that have referred to Lovász according to the Web of Science citation service. We study the scientific influence of László Lovász as seen through this collaboration network. Here, we provide some statistical features of these publications, as well as the characteristics of the co-authorship network using standard social network analysis techniques.

Let $G=(V,E)$ be a simple graph with vertex set $V$ and edge set $E$. If $k\ge 2$ is an integer, then the signed edge $k$-independence function of $G$ is a function $f:E\to \{-1,1\}$ such that $\sum _{e^{\prime }\in N[e]}f(e^{\prime })\le k–1$ for each $e\in E$. The weight of a signed edge $k$-independence function $f$ is $\omega (f)=\sum _{e\in E}f(e).$ The signed edge $k$-independence number ${\alpha }_k^s(G)$ of $G$ is the maximum weight of a signed edge $k$-independence function of $G$. In this paper, we initiate the study of the signed edge $k$-independence number and we present bounds for this parameter. In particular, we determine this parameter for some classes of graphs.

Let $S=S_1{S}_2{S}_3\dots S_n$ be a finite string which can be written in the form $X_1^{k_1}{X}_2^{k_2}\dots X_r^{k_r}$, where $X_i^{k_i}$ is the $k_i$ copies of a non-empty string $X_i$ and each $k_i$ is a non-negative integer. Then, the curling number of the string $S$, denoted by $\text{cn}(S)$, is defined to be $\text{cn}(S)=max\{k_i:1\le i\le r\}$. Analogous to this concept, the degree sequence of the graph $G$ can be written as a string $X_1^{k_1}\circ X_2^{k_2}\circ X_3^{k_3}\circ \cdots \circ X_r^{k_r}$. The compound curling number of $G$, denoted ${\text{cn}}^c(G)$, is defined to be ${\text{cn}}^c(G)=\prod _{i=1}^r{k}_i.$ In this paper, the curling number and compound curling number of the powers of the Mycielskian of certain graphs are discussed.

The symmetric inverse monoid, $\text{SIM}(n)$, is the set of all partial one-to-one mappings from the set $\{1,2,\dots ,n\}$ to itself under the operation of composition. Earlier research on the symmetric inverse monoid delineated the process for determining whether an element of $\text{SIM}(n)$ has a $k$th root. The problem of enumerating $k$th roots of a given element of $\text{SIM}(n)$ has since been posed, which is solved in this work. In order to find the number of $k$th roots of an element, all that is needed is to know the cycle and path structure of the element. Conveniently, the cycle and cycle-free components may be considered separately in calculating the number of $k$th roots. Since the enumeration problem has been completed for the symmetric group, this paper only focuses on the cycle-free elements of $\text{SIM}(n)$. The formulae derived for cycle-free elements of $\text{SIM}(n)$ here utilize integer partitions, similar to their use in the expressions given for the number of $k$th roots of permutations.

Motivated by finding a way to connect the Roman domination number and 2-domination number, which are in general not comparable, we consider a parameter called the Italian domination number (also known as the Roman $(2)$-domination number). This parameter is bounded above by each of the other two. Bounds on the Italian domination number in terms of the order of the graph are shown. The value of the Italian domination number is studied for several classes of graphs. We also compare the Italian domination number with the 2-domination number.

The 3-sphere regular cellulation conjecture claims that every 2-connected cyclic graph is the 1-dimensional skeleton of a regular cellulation of the 3-dimensional sphere. The conjecture is obviously true for planar graphs. 2-connectivity is a necessary condition for a graph to satisfy such a property. Therefore, the question whether a graph is the 1-dimensional skeleton of a regular cellulation of the 3-dimensional sphere would be equivalent to the 2-connectivity test if the conjecture were proved to be true. On the contrary, it is not even clear whether such a decision problem is computationally tractable.

We introduced a new class of graphs called weakly-split and proved the conjecture for such a class. Hamiltonian, split, complete $k$-partite, and matrogenic cyclic graphs are weakly split. In this paper, we introduce another class of graphs for which the conjecture is true. Such a class is a superclass of planar graphs and weakly-split graphs.

The maximum number of internal disjoint paths between any two distinct nodes of faulty enhanced hypercube $Q_{n,k}(1\le k\le n-1)$ are considered in a more flexible approach. Using the structural properties of $Q_{n,k}(1\le k\le n-1)$, $min(d_{Q_{n,k}-V}(x),d_{Q_{n,k}-V}(y))$ disjoint paths connecting two distinct vertices $x$ and $y$ in an $n$-dimensional faulty enhanced hypercube $Q_{n,k}-V(n\ge 8,k\ne n-2,n-1)$ are conformed when $|V^{\prime }|$ is at most $n-1$. Meanwhile, it is proved that there exists $min(d_{Q_{n,k}-V}(x),d_{Q_{n,k}-V}(y))$ internal disjoint paths between $x$ and $y$ in $Q_{n,k}-V(n\ge 8,k\ne n-2,n-1)$, under the constraints that (1) The number of faulty vertices is no more than $2n-3$; (2) Every vertex in $Q_{n,k}-V^{\prime }$ is incident to at least two fault-free vertices. This results generalize the results of the faulted hypercube $F{Q}_n$, which is a special case of $Q_{n,k}$, and have improved the theoretical evidence of the fact that $Q_{n,k}$ has excellent node-fault-tolerance when used as a topology of large-scale computer networks, thus remarkably improving the performance of the interconnect networks.

Given a finite non-empty sequence $S$ of integers, write it as $X{Y}^k$, consisting of a prefix $X$ (which may be empty), followed by $k$ copies of a non-empty string $Y$. Then, the greatest such integer $k$ is called the curling number of $S$ and is denoted by $cn(S)$. The notion of curling number of graphs has been introduced in terms of their degree sequences, analogous to the curling number of integer sequences. In this paper, we study the curling number of certain graph classes and graphs associated to given graph classes.

In this paper, we investigate and obtain the properties of higher-order Daehee sequences by using generating functions. In particular, by means of the method of coefficients and generating functions, we establish some identities involving higher-order Daehee numbers, generalized Cauchy numbers, Lah numbers, Stirling numbers of the first kind, unsigned Stirling numbers of the first kind, generalized harmonic polynomials and the numbers $P(r,n,k)$.

In this paper, we give the sufficient conditions for a graph with large minimum degree to be $s$-connected, $s$-edge-connected, $\beta$-deficient, $s$-path-coverable, $s$-Hamiltonian and $s$-edge-Hamiltonian in terms of spectral radius of its complement.

The maximum number of clues in an $n\times n$ American-style crossword puzzle grid is explored. Grid constructions provided for all $n$ are proved to be maximal for all even $n$. By using mixed integer linear programming, they are verified to be maximal for all odd $n\le 49$. Further, for all $n\le 30$, all maximal grids are provided.

For a graph $G$, the Merrifield-Simmons index $i(G)$ is defined as the total number of its independent sets. In this paper, we determine sharp upper and lower bounds on Merrifield-Simmons index of generalized $\theta$-graph, which is obtained by subdividing the edges of the multigraph consisting of $k$ parallel edges, denoted by $\theta (r_1,r_2,\dots ,r_k)$. The corresponding extremal graphs are also characterized.

For a non-simply connected orthogonal polygon $T$, assume that $T=S\setminus (A_1\cup \dots \cup A_n)$, where $S$ is a simply connected orthogonal polygon and where $A_1,\dots ,A_n$ are pairwise disjoint sets, each the connected interior of an orthogonal polygon, $A_i\subset S,1\le i\le n$. If set $T$ is staircase starshaped, then $\text{Ker }T=\bigcap \{\text{Ker }(S\setminus A_i):1\le i\le n\}$. Moreover, each component of this kernel will be the intersection of the nonempty staircase convex set $\text{Ker }S$ with a box, providing an easy proof that each of these components is staircase convex. Finally, there exist at most $(n+1{)}^2$ such components, and the bound $(n+1{)}^2$ is best possible.

We empirically evaluate the performance of three approximation algorithms for the online bottleneck matching problem. In this matching problem, $k$ server-vertices lie in a metric space and $k$ request-vertices that arrive over time each must immediately be permanently assigned to a server-vertex. The goal is to minimize the maximum distance between any request and its assigned server. We consider the naïve \textsc{Greedy} algorithm, as well as \textsc{Permutation} and \textsc{Balance}, each of which were constructed to counter certain challenges in the online problem. We analyze the performance of each algorithm on a variety of data sets, considering each both in the original model, where applicable, and in the resource augmentation setting when an extra server is introduced at each server-vertex. While no algorithm strictly dominates, \textsc{Greedy} frequently performs the best, and thus is recommended due to its simplicity.

In this paper, we study the total domatic partition problem for bipartite graphs, split graphs, and graphs with balanced adjacency matrices. We show that the total domatic partition problem is NP-complete for bipartite graphs and split graphs, and show that the total domatic partition problem is polynomial-time solvable for graphs with balanced adjacency matrices. Furthermore, we show that the total domatic partition problem is linear-time solvable for any chordal bipartite graph $G$ if a $\mathrm{\Gamma }$-free form of the adjacency matrix of $G$ is given.