Several authors have studied the graphs for which every edge is a chord of a cycle; among 2-connected graphs, one characterization is that the deletion of one vertex never creates a cut-edge. Two new results: among 3-connected graphs with minimum degree at least 4, every two adjacent edges are chords of a common cycle if and only if deleting two vertices never creates two adjacent cut-edges; among 4-connected graphs, every two edges are always chords of a common cycle.

A path-neighborhood graph is a connected graph in which every neighborhood induces a path. In the main results the 3-sun-free path-neighborhood graphs are characterized. The 3-sun is obtained from a 6-cycle by adding three chords between the three pairs of vertices at distance 2. A Pk-graph is a path-neighborhood graph in which every neighborhood is a Pk, where Pk is the path on k vertices. The Pk-graphs are characterized for k ≤ 4.

An edge-colored graph $G$ is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph $G$, denoted by $\mathrm{pc}\left(G\right)$, is the smallest number of colors that are needed to color the edges of $G$ in order to make it proper connected. In this paper, we obtain the sharp upper bound for $\mathrm{pc}\left(G\right)$ of a general bipartite graph $G$ and a series of extremal graphs. Additionally, we give a proper $2$-coloring for a connected bipartite graph $G$ having $\delta \left(G\right)\ge 2$ and a dominating cycle...

In this paper, the upper and lower bounds for the quotient of spectral radius (Laplacian spectral radius, signless Laplacian spectral radius) and the clique number together with the corresponding extremal graphs in the class of connected graphs with $n$ vertices and clique number $\omega$$(2\le ...$

The eccentricity $e\left(v\right)$ of a vertex $v$ is defined as the distance to a farthest vertex from $v$. The radius of a graph $G$ is defined as a $r\left(G\right)={min}_{u\in V\left(G\right)}\left\{e\left(u\right)\right\}$. A graph $G$ is radius-edge-invariant if $r(G-e)=r\left(G\right)$ for every $e\in E\left(G\right)$, radius-vertex-invariant if $r(G-v)=r\left(G\right)$ for every $v\in V\left(G\right)$ and radius-adding-invariant if $r(G+e)=r\left(G\right)$ for every $e\in E\left(\overline{G}\right)$. Such classes of graphs are studied in this paper.

Let Γn be the complete undirected Cayley graph of the odd cyclic group Zn. Connected graphs whose vertices are rainbow tetrahedra in Γn are studied, with any two such vertices adjacent if and only if they share (as tetrahedra) precisely two distinct triangles. This yields graphs G of largest degree 6, asymptotic diameter |V (G)|1/3 and almost all vertices with degree: (a) 6 in G; (b) 4 in exactly six connected subgraphs of the (3, 6, 3, 6)-semi- regular tessellation; and (c) 3 in exactly four connected...

Let L be the set of all hereditary and additive properties of graphs. For P₁, P₂ ∈ L, the reducible property R = P₁∘P₂ is defined as follows: G ∈ R if and only if there is a partition V(G) = V₁∪ V₂ of the vertex set of G such that $⟨V₁{⟩}_G\in P₁$ and $⟨V₂{⟩}_G\in P₂$. The aim of this paper is to investigate the structure of the reducible properties of graphs with emphasis on the uniqueness of the decomposition of a reducible property into irreducible ones.

Let $G$ be a graph with $n$ vertices, $m$ edges and a vertex degree sequence $(d_1,d_2,\cdots ,d_n)$, where $d_1\ge d_2\ge \cdots \ge d_n$. The spectral radius and the largest Laplacian eigenvalue are denoted by $\rho \left(G\right)$ and $\mu \left(G\right)$, respectively. We determine the graphs with $$\rho \left(G\right)=\frac{d_n-1}{2}+\sqrt{2m-n{d}_n+\frac{{(d_n+1)}^2}{4}}$$ and the graphs with $d_n\ge 1$ and $$\mu \left(G\right)=d_n+\frac{1}{2}+\sqrt{{\sum }_{i=1}^n{d}_i(d_i-d_n)+{\left(d_n-\frac{1}{2}\right)}^2}.$$ We also present some sharp lower bounds for the Laplacian eigenvalues of a connected graph.

We consider the problem of the existence of uniquely partitionable planar graphs. We survey some recent results and we prove the nonexistence of uniquely (𝓓₁,𝓓₁)-partitionable planar graphs with respect to the property 𝓓₁ "to be a forest".

For any nontrivial connected graph $F$ and any graph $G$, the $F$-degree of a vertex $v$ in $G$ is the number of copies of $F$ in $G$ containing $v$. $G$ is called $F$-continuous if and only if the $F$-degrees of any two adjacent vertices in $G$ differ by at most 1; $G$ is $F$-regular if the $F$-degrees of all vertices in $G$ are the same. This paper classifies all $P_4$-continuous graphs with girth greater than 3. We show that for any nontrivial connected graph $F$ other than the star $K_{1,k}$, $k\ge 1$, there exists a regular graph that is not...

A graph H is obtained from a graph G by an edge rotation if G contains three distinct vertices u,v, and w such that uv ∈ E(G), uw ∉ E(G), and H = G-uv+uw. A graph H is obtained from a graph G by an edge jump if G contains four distinct vertices u,v,w, and x such that uv ∈ E(G), wx∉ E(G), and H = G-uv+wx. If a graph H is obtained from a graph G by a sequence of edge jumps, then G is said to be j-transformed into H. It is shown that for every two graphs G and H of the same order (at least 5) and same...