On Szeged Polynomial of Graphs with Even Number of Vertices

Abstract

The Szeged polynomial of a connected graph $G$ is defined as $S_z(G,x)=\sum _{e\in E(G)}{x}^{n_{u(e)n_v(e)}}$, where $n_u(e)$ is the number of vertices of $G$ lying closer to $u$ than to $v$, and $n_v(e)$ is the number of vertices of $G$ lying closer to $v$ than to $u$. Ashrafi et al. (On Szeged polynomial of a graph, Bull. Iran. Math. Soc. $33(2007)37-46)$ proved that if $|V(G)|$ is even, then $\mathrm{deg}(S_z(G,x))\le \frac{1}{4}|V(G{)}^2|$. In this paper, we investigate the structure of graphs with an even number of vertices for which equality holds, and also examine equality for the sum of graphs.