Let G be a graph. A function f : V (G) → {−1, 1} is a signed k- independence function if the sum of its function values over any closed neighborhood is at most k − 1, where k ≥ 2. The signed k-independence number of G is the maximum weight of a signed k-independence function of G. Similarly, the signed total k-independence number of G is the maximum weight of a signed total k-independence function of G. In this paper, we present new bounds on these two parameters which improve some existing bounds....

Let $G=(V,E)$, $V=\{v_1,v_2,...,v_n\}$, be a simple connected graph with $n$ vertices, $m$ edges and a sequence of vertex degrees $d_1\ge d_2\ge \cdots \ge d_n$. Denote by $A$ and $D$ the adjacency matrix and diagonal vertex degree matrix of $G$, respectively. The signless Laplacian of $G$ is defined as $L^{+}=D+A$ and the normalized signless Laplacian matrix as ${ℒ}^{+}=D^{-1/2}{L}^{+}{D}^{-1/2}$. The normalized signless Laplacian spreads of a connected nonbipartite graph $G$ are defined as $r\left(G\right)={\gamma }_2^{+}/{\gamma }_n^{+}$ and $l\left(G\right)={\gamma }_2^{+}-{\gamma }_n^{+}$, where ${\gamma }_1^{+}\ge {\gamma }_2^{+}\ge \cdots \ge {\gamma }_n^{+}\ge 0$ are eigenvalues of ${ℒ}^{+}$. We establish sharp lower and upper bounds for the normalized signless Laplacian spreads...

A graph is determined by its signless Laplacian spectrum if no other non-isomorphic graph has the same signless Laplacian spectrum (simply $G$ is $DQS$). Let $T(a,b,c)$ denote the $T$-shape tree obtained by identifying the end vertices of three paths $P_{a+2}$, $P_{b+2}$ and $P_{c+2}$. We prove that its all line graphs $ℒ\left(T\right(a,b,c\left)\right)$ except $ℒ\left(T\right(t,t,2t+1\left)\right)$ ($t\ge 1$) are $DQS$, and determine the graphs which have the same signless Laplacian spectrum as $ℒ\left(T\right(t,t,2t+1\left)\right)$. Let ${\mu }_1\left(G\right)$ be the maximum signless Laplacian eigenvalue of the graph $G$. We give the limit of ${\mu }_1\left(ℒ\left(T(a,b,c)\right)\right)$, too.

A simplex of a graph G is a subgraph of G which is a complete graph. The simplex graph Simp(G) of G is the graph whose vertex set is the set of all simplices of G and in which two vertices are adjacent if and only if they have a non-empty intersection. The simplex graph operator is the operator which to every graph G assigns its simplex graph Simp(G). The paper studies graphs which are fixed in this operator and gives a partial answer to a problem suggested by E. Prisner.

Let $A\left(G\right)$ be the adjacency matrix of $G$. The characteristic polynomial of the adjacency matrix $A$ is called the characteristic polynomial of the graph $G$ and is denoted by $\phi (G,\lambda )$ or simply $\phi \left(G\right)$. The spectrum of $G$ consists of the roots (together with their multiplicities) ${\lambda }_1\left(G\right)\ge {\lambda }_2\left(G\right)\ge ...\ge {\lambda }_n\left(G\right)$ of the equation $\phi (G,\lambda )=0$. The largest root ${\lambda }_1\left(G\right)$ is referred to as the spectral radius of $G$. A $‡$-shape is a tree with exactly two of its vertices having maximal degree 4. We will denote by $G(l_1,l_2,...,l_7)$$...$

A property P defined on all graphs of order n is said to be k-stable if for any graph of order n that does not satisfy P, the fact that uv is not an edge of G and that G + uv satisfies P implies $d_G\left(u\right)+d_G\left(v\right)<k$. Every property is (2n-3)-stable and every k-stable property is (k+1)-stable. We denote by s(P) the smallest integer k such that P is k-stable and call it the stability of P. This number usually depends on n and is at most 2n-3. A graph of order n is said to be pancyclic if it contains cycles of all lengths...

In this paper, we study the Steiner 2-edge connected subgraph polytope. We introduce a large class of valid inequalities for this polytope called the generalized Steiner F-partition inequalities, that generalizes the so-called Steiner F-partition inequalities. We show that these inequalities together with the trivial and the Steiner cut inequalities completely describe the polytope on a class of graphs that generalizes the wheels. We also describe necessary conditions for these inequalities to...

Let G be a connected graph. A vertex w ∈ V.G/ strongly resolves two vertices u,v ∈ V.G/ if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set S of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong resolving set for G is called the strong metric dimension of G. It is well known that the problem of computing this invariant is NP-hard. In this paper we study...

A vertex colouring of a 2-connected plane graph G is a strong parity vertex colouring if for every face f and each colour c, the number of vertices incident with f coloured by c is either zero or odd. Czap et al. in [9] proved that every 2-connected plane graph has a proper strong parity vertex colouring with at most 118 colours. In this paper we improve this upper bound for some classes of plane graphs.