A subset of vertices of a graph G is k-independent if it induces in G a subgraph of maximum degree less than k. The minimum and maximum cardinalities of a maximal k-independent set are respectively denoted iₖ(G) and βₖ(G). We give some relations between βₖ(G) and ${\beta }_j\left(G\right)$ and between iₖ(G) and $i_j\left(G\right)$ for j ≠ k. We study two families of extremal graphs for the inequality i₂(G) ≤ i(G) + β(G). Finally we give an upper bound on i₂(G) and a lower bound when G is a cactus.

In this paper we investigate the hypergraphs whose spectral radii attain the maximum among all uniform hypergraphs with given number of edges. In particular we characterize the hypergraph(s) with maximum spectral radius over all unicyclic hypergraphs, linear or power unicyclic hypergraphs with given girth, linear or power bicyclic hypergraphs, respectively.

Given a graph $G$, let $f\left(G\right)$ denote the maximum number of edges in a bipartite subgraph of $G$. Given a fixed graph $H$ and a positive integer $m$, let $f(m,H)$ denote the minimum possible cardinality of $f\left(G\right)$, as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$. In this paper we prove that $f(m,{\theta }_{k,s})\ge \frac{1}{2}m+\Omega \left(m^{(2k+1)/(2k+2)}\right)$, which extends the results of N. Alon, M. Krivelevich, B. Sudakov. Write $K_k^{\text{'}}$ and $K_{t,s}^{\text{'}}$ for the subdivisions of $K_k$ and $K_{t,s}$. We show that $f(m,K_k^{\text{'}})\ge \frac{1}{2}m+\Omega \left(m^{(5k-8)/(6k-10)}\right)$ and $f(m,K_{t,s}^{\text{'}})\ge \frac{1}{2}m+\Omega \left(m^{(5t-1)/(6t-2)}\right)$, improving a result of Q. Zeng, J. Hou. We also give lower bounds on wheel-free graphs....

For a graph G = (V,E) and a vertex v ∈ V , let T(v) be a local trace at v, i.e. T(v) is an Eulerian subgraph of G such that every walk W(v), with start vertex v can be extended to an Eulerian tour in T(v). We prove that every maximum edge-disjoint cycle packing Z* of G induces a maximum trace T(v) at v for every v ∈ V . Moreover, if G is Eulerian then sufficient conditions are given that guarantee that the sets of cycles inducing maximum local traces of G also induce a maximum cycle packing of G....

An r-maximum k-edge-coloring of G is a k-edge-coloring of G having a property that for every vertex v of degree dG(v) = d, d ≥ r, the maximum color, that is present at vertex v, occurs at v exactly r times. The r-maximum index [...] χr′(G) ${\chi }_r^{\text{'}}\left(G\right)$ is defined to be the minimum number k of colors needed for an r-maximum k-edge-coloring of graph G. In this paper we show that [...] χr′(G)≤3 ${\chi }_r^{\text{'}}\left(G\right)\le 3$ for any nontrivial connected graph G and r = 1 or 2. The bound 3 is tight. All graphs G with [...] χ1′(G)=i ${\chi }_1^{\text{'}}\left(G\right)=i$ , i...

We show that an n-vertex hypergraph with no r-regular subgraphs has at most 2n−1+r−2 edges. We conjecture that if n > r, then every n-vertex hypergraph with no r-regular subgraphs having the maximum number of edges contains a full star, that is, 2n−1 distinct edges containing a given vertex. We prove this conjecture for n ≥ 425. The condition that n > r cannot be weakened.

The direct product of graphs G = (V (G),E(G)) and H = (V (H),E(H)) is the graph, denoted as G×H, with vertex set V (G×H) = V (G)×V (H), where vertices (x1, y1) and (x2, y2) are adjacent in G × H if x1x2 ∈ E(G) and y1y2 ∈ E(H). Let n be odd and m even. We prove that every maximum independent set in Pn×G, respectively Cm×G, is of the form (A×C)∪(B× D), where C and D are nonadjacent in G, and A∪B is the bipartition of Pn respectively Cm. We also give a characterization of maximum independent subsets...