For a nontrivial connected graph $G$, let $cV\left(G\right)\to \mathbb{N}$ be a vertex coloring of $G$ where adjacent vertices may be colored the same. For a vertex $v$ of $G$, the neighborhood color set $\mathrm{NC}\left(v\right)$ is the set of colors of the neighbors of $v$. The coloring $c$ is called a set coloring if $\mathrm{NC}\left(u\right)\ne \mathrm{NC}\left(v\right)$ for every pair $u,v$ of adjacent vertices of $G$. The minimum number of colors required of such a coloring is called the set chromatic number ${\chi }_s\left(G\right)$. A study is made of the set chromatic number of the join $G+H$ of two graphs $G$ and $H$. Sharp lower and upper bounds...

The generalized k-connectivity κk(G) of a graph G was introduced by Hager in 1985. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k-edge-connectivity which is defined as λk(G) = min{λ(S) : S ⊆ V (G) and |S| = k}, where λ(S) denote the maximum number ℓ of pairwise edge-disjoint trees T1, T2, . . . , Tℓ in G such that S ⊆ V (Ti) for 1 ≤ i ≤ ℓ. In this paper, we study the generalized edge- connectivity of product graphs and obtain sharp upper bounds...

Let G = (V (G),E(G)) be a simple strongly connected digraph and q(G) be the signless Laplacian spectral radius of G. For any vertex vi ∈ V (G), let d+i denote the outdegree of vi, m+i denote the average 2-outdegree of vi, and N+i denote the set of out-neighbors of vi. In this paper, we prove that: (1) (1) q(G) = d+1 +d+2 , (d+1 ≠ d+2) if and only if G is a star digraph [...] ,where d+1, d+2 are the maximum and the second maximum outdegree, respectively [...] is the digraph on n vertices obtained...

Let $G$ be a group and let $X$ be a finite subset. The isoperimetric method investigates the objective function $\left|\right(XB)\setminus X|$, defined on the subsets $X$ with $\left|X\right|\ge k$ and $|G\setminus (XB\left)\right|\ge k$, where $XB$ is the product of $X$ by $B$.In this paper we present all the basic facts about the isoperimetric method. We improve some of our previous results and obtain generalizations and short proofs for several known results. We also give some new applications.Some of the results obtained here will be used in coming papers to improve Kempermann structure...

We consider Stanley-Reisner rings $k[x_1,...,x_n]/I\left(\mathscr{H}\right)$ where $I\left(\mathscr{H}\right)$ is the edge ideal associated to some particular classes of hypergraphs. For instance, we consider hypergraphs that are natural generalizations of graphs that are lines and cycles, and for these we compute the Betti numbers. We also generalize some known results about chordal graphs and study a weak form of shellability.

Let S be a cut of a simple connected graph G. If S has no proper subset that is a cut, we say S is a minimal cut of G. To a minimal cut S, a connected component of G-S is called a fragment. And a fragment with no proper subset that is a fragment is called an end. In the paper ends are characterized and it is proved that to a connected graph G = (V,E), the number of its ends Σ ≤ |V(G)|.

Let T be a tree, a vertex of degree one and a vertex of degree at least three is called a leaf and a branch vertex, respectively. The set of leaves of T is denoted by Leaf(T). The subtree T − Leaf(T) of T is called the stem of T and denoted by Stem(T). In this paper, we give two sufficient conditions for a connected graph to have a spanning tree whose stem has a bounded number of branch vertices, and these conditions are best possible.

In this paper, we propose a method which enables to construct almost optimal broadcast schemes on an $n$-dimensional hypercube in the circuit switched, $\Delta$-port model. In this model, an initiator must inform all the nodes of the network in a sequence of rounds. During a round, vertices communicate along arc-disjoint dipaths. Our construction is based on particular sequences of nested binary codes having the property that each code can inform the next one in a single round. This last property is insured...