Search

For some positive integer $m$, a real polynomial $P(x)=\sum\limits_{k=0}^ma_kx^k$ with $a_k\geqslant 0$ is called log-concave (resp. ultra log-concave) if $a_k^2\geqslant a_{k-1}a_{k+1}$ (resp. $a_k^2\geqslant \left(1+\frac{1}{k}\right)\left(1+\frac{1}{m-k}\right)\cdot$ $a_{k-1}a_{k+1}$) for all $1\leqslant k\leqslant m-1$. If $P(x)$ has only real roots, then it is called real-rooted. It is well-known that the conditions of log-concavity, ultra log-concavity and real-rootedness are ever-stronger. For a graph $G$, a dependent set is a set of vertices which is not independent, i.e., the set of vertices whose induced subgraph contains at least one edge. The dependence polynomial of $G$ is defined as $D(G, x):=\sum\limits_{k\geqslant 0}d_k(G)x^k$, where $d_k(G)$ is the number of dependent sets of size $k$ in $G$. Horrocks proved that $D(G, x)$ is log-concave for every graph $G$ [J. Combin. Theory, Ser. B, 84 (2002) 180--185]. In the present paper, we prove that, for a graph $G$, $D(G, x)$ is ultra log-concave if $G$ is $(K_2\cup 2K_1)$-free or contains an independent set of size $|V(G)|-2$, and give the characterization of graphs whose dependence polynomials are real-rooted. Finally, we focus more attention to the problems of log-concavity about independence systems and pose several conjectures closely related the famous Mason's Conjecture., Comment: 17 pages, 5 figures

Let $G$ be a connected graph. The resistance distance between two vertices $u$ and $v$ of $G$, denoted by $R_{G}[u,v]$, is defined as the net effective resistance between them in the electric network constructed from $G$ by replacing each edge with a unit resistor. The resistance diameter of $G$, denoted by $D_{r}(G)$, is defined as the maximum resistance distance among all pairs of vertices of $G$. Let $P_n=a_1a_2\ldots a_n$ be the $n$-vertex path graph and $C_{4}=b_{1}b_2b_3b_4b_{1}$ be the 4-cycle. Then the $n$-th block tower graph $G_n$ is defined as the the Cartesian product of $P_n$ and $C_4$, that is, $G_n=P_{n}\square C_4$. Clearly, the vertex set of $G_n$ is $\{(a_i,b_j)|i=1,\ldots,n;j=1,\ldots,4\}$. In [Discrete Appl. Math. 320 (2022) 387--407], Evans and Francis proposed the following conjecture on resistance distances of $G_n$ and $G_{n+1}$: \begin{equation*} \lim_{n \rightarrow \infty}\left(R_{G_{n+1}}[(a_{1},b_1),(a_{n+1},b_3)]-R_{G_{n}}[(a_{1},b_1),(a_{n},b_3)]\right)=\frac{1}{4}. \end{equation*} In this paper, combining algebraic methods and electrical network approaches, we confirm and further generalize this conjecture. In addition, we determine all the resistance diametrical pairs in $G_n$, which enables us to give an equivalent explanation of the conjecture., Comment: 19 pages,8 figures

A perfect code in a graph is an independent set of the graph such that every vertex outside the set is adjacent to exactly one vertex in the set. A circulant graph is a Cayley graph of a cyclic group. In this paper we study perfect codes in circulant graphs of degree $p^l - 1$, where $p$ is a prime and $l \ge 1$. We obtain a necessary and sufficient condition for such a circulant graph to admit perfect codes, give a construction of all such circulant graphs which admit perfect codes, and prove a lower bound on the number of distinct perfect codes in such a circulant graph. This extends known results for the case $l=1$ and provides insight on the general problem on the existence and structure of perfect codes in circulant graphs.

A graph pair $(\Gamma, \Sigma)$ is called stable if $\aut(\Gamma)\times\aut(\Sigma)$ is isomorphic to $\aut(\Gamma\times\Sigma)$ and unstable otherwise, where $\Gamma\times\Sigma$ is the direct product of $\Gamma$ and $\Sigma$. A graph is called $R$-thin if distinct vertices have different neighbourhoods. $\Gamma$ and $\Sigma$ are said to be coprime if there is no nontrivial graph $\Delta$ such that $\Gamma \cong \Gamma_1 \times \Delta$ and $\Sigma \cong \Sigma_1 \times \Delta$ for some graphs $\Gamma_1$ and $\Sigma_1$. An unstable graph pair $(\Gamma, \Sigma)$ is called nontrivially unstable if $\Gamma$ and $\Sigma$ are $R$-thin connected coprime graphs and at least one of them is non-bipartite. This paper contributes to the study of the stability of graph pairs with a focus on the case when $\Sigma = C_n$ is a cycle. We give two sufficient conditions for $(\Gamma, C_n)$ to be nontrivially unstable, where $n \ne 4$ and $\Gamma$ is an $R$-thin connected graph. In the case when $\Gamma$ is an $R$-thin connected non-bipartite graph, we obtain the following results: (i) if $(\Gamma, K_2)$ is unstable, then $(\Gamma, C_{n})$ is unstable for every even integer $n \geq 4$; (ii) if an even integer $n \ge 6$ is compatible with $\Gamma$ in some sense, then $(\Gamma, C_{n})$ is nontrivially unstable if and only if $(\Gamma, K_2)$ is unstable; (iii) if there is an even integer $n \ge 6$ compatible with $\Gamma$ such that $(\Gamma, C_{n})$ is nontrivially unstable, then $(\Gamma, C_{m})$ is unstable for all even integers $m \ge 6$. We also prove that if $\Gamma$ is an $R$-thin connected graph and $n \ge 3$ is an odd integer compatible with $\Gamma$, then $(\Gamma, C_{n})$ is stable.

Let $\Ga = (V, E)$ be a graph and $a, b$ nonnegative integers. An $(a, b)$-regular set in $\Ga$ is a nonempty proper subset $D$ of $V$ such that every vertex in $D$ has exactly $a$ neighbours in $D$ and every vertex in $V \setminus D$ has exactly $b$ neighbours in $D$. A $(0,1)$-regular set is called a perfect code, an efficient dominating set, or an independent perfect dominating set. A subset $D$ of a group $G$ is called an $(a,b)$-regular set of $G$ if it is an $(a, b)$-regular set in some Cayley graph of $G$, and an $(a, b)$-regular set in a Cayley graph of $G$ is called a subgroup $(a, b)$-regular set if it is also a subgroup of $G$. In this paper we study $(a, b)$-regular sets in Cayley graphs with a focus on $(0, k)$-regular sets, where $k \ge 1$ is an integer. Among other things we determine when a non-trivial proper normal subgroup of a group is a $(0, k)$-regular set of the group. We also determine all subgroup $(0, k)$-regular sets of dihedral groups and generalized quaternion groups. We obtain necessary and sufficient conditions for a hypercube or the Cartesian product of $n$ copies of the cycle of length $p$ to admit $(0, k)$-regular sets, where $p$ is an odd prime. Our results generalize several known results from perfect codes to $(0, k)$-regular sets., Comment: 27 pages

For a graph $G$, the edge Mostar index of $G$ is the sum of $|m_u(e|G)-m_v(e|G)|$ over all edges $e=uv$ of $G$, where $m_u(e|G)$ denotes the number of edges of $G$ that have a smaller distance in $G$ to $u$ than to $v$, and analogously for $m_v(e|G)$. This paper mainly studies the problem of determining the graphs that maximize the edge Mostar index among tricyclic graphs. To be specific, we determine a sharp upper bound for the edge Mostar index on tricyclic graphs and identify the graphs that attain the bound., Comment: arXiv admin note: substantial text overlap with arXiv:2306.02761

For a graph $G$, the Mostar index of $G$ is the sum of $|n_u(e)$ - $n_v(e)|$ over all edges $e=uv$ of $G$, where $n_u(e)$ denotes the number of vertices of $G$ that have a smaller distance in $G$ to $u$ than to $v$, and analogously for $n_v(e)$. We determine all the graphs that maximize and minimize the Mostar index respectively over all trees in terms of some fixed parameters like the number of odd vertices, the number of vertices of degree two, and the number of pendent paths of fixed length.

For a given connected graph $G$, the edge Mostar index $Mo_e(G)$ is defined as $Mo_e(G)=\sum_{e=uv \in E(G)}|m_u(e|G) - m_v(e|G)|$, where $m_u(e|G)$ and $m_v(e|G)$ are respectively, the number of edges of $G$ lying closer to vertex $u$ than to vertex $v$ and the number of edges of $G$ lying closer to vertex $v$ than to vertex $u$. We determine a sharp upper bound for the edge Mostar index on bicyclic graphs and identify the graphs that attain the bound, which disproves a conjecture proposed by Liu et al. [Iranian J. Math. Chem. 11(2) (2020) 95--106]., Comment: Completed before 10 May 2023

Partial cubes are the graphs which can be embedded into hypercubes. The {\em cube polynomial} of a graph $G$ is a counting polynomial of induced hypercubes of $G$, which is defined as $C(G,x):=\sum_{i\geqslant 0}\alpha_i(G)x^i$, where $\alpha_i(G)$ is the number of induced $i$-cubes (hypercubes of dimension $i$) of $G$. The {\em clique polynomial} of $G$ is defined as $Cl(G,x):=\sum_{i\geqslant 0}a_i(G)x^i$, where $a_i(G)$ ($i\geqslant 1$) is the number of $i$-cliques in $G$ and $a_0(G)=1$. Equivalently, $Cl(G, x)$ is exactly the independence polynomial of the complement $\overline{G}$ of $G$. The {\em crossing graph} $G^{\#}$ of a partial cube $G$ is the graph whose vertices are corresponding to the $\Theta$-classes of $G$, and two $\Theta$-classes are adjacent in $G^{\#}$ if and only if they cross in $G$. In the present paper, we prove that for a partial cube $G$, $C(G,x)\leqslant Cl(G^{\#}, x+1)$ and the equality holds if and only if $G$ is a median graph. Since every graph can be represented as the crossing graph of a median graph [SIAM J. Discrete Math., 15 (2002) 235--251], the above necessary-and-sufficient result shows that the study on the cube polynomials of median graphs can be transformed to the one on the clique polynomials of general graphs (equivalently, on the independence polynomials of their complements). In addition, we disprove the conjecture that the cube polynomials of median graphs are unimodal., Comment: 13 pages,2 figures

Partial cubes are graphs that can be isometrically embedded into hypercubes. Convex cycles play an important role in the study of partial cubes. In this paper, we prove that a regular partial cube is a hypercube (resp., a doubled Odd graph, an even cycle of length $2n$ where $n\geqslant 4$) if and only if all its convex cycles are 4-cycles (resp., 6-cycles, $2n$-cycles). In particular, the partial cubes whose all convex cycles are 4-cycles are equivalent to almost-median graphs, so we obtain that regular almost-median graphs are exactly hypercubes, which generate the result by Mulder [J. Graph Theory, 4 (1980) 107--110] -- regular median graphs are hypercubes., Comment: 8 pages, 0 figures

Comparability graphs are a popular class of graphs. We introduce as the digraph analogue of comparability graphs the class of comparability digraphs. We show that many concepts such as implication classes and the knotting graph for a comparability graph can be naturally extended to a comparability digraph. We give a characterization of comparability digraphs in terms of their knotting graphs. Semicomplete comparability digraphs are a prototype of comparability digraphs. One instrumental technique for analyzing the structure of comparability graphs is the Triangle Lemma for graphs. We generalize the Triangle Lemma to semicomplete digraphs. Using the Triangle Lemma for semicomplete digraphs we prove that if an implication class of a semicomplete digraph contains no circuit of length 2 then it contains no circuit at all. We also use it to device an $\mathcal{O}(n^3)$ time recognition algorithm for semicomplete comparability digraphs where $n$ is the number of vertices of the input digraph. The correctness of the algorithm implies a characterization for semicomplete comparability digraphs, akin to that for comparability graphs., Comment: 22 pages, 4 figures, 1 algorithm

For a graph $G = (V, E)$ with vertex set $V$ and edge set $E$, a subset $F$ of $E$ is called an $\emph{edge dominating set}$ (resp. a $\emph{total edge dominating set}$) if every edge in $E\backslash F$ (resp. in $E$) is adjacent to at least one edge in $F$, the minimum cardinality of an edge dominating set (resp. a total edge dominating set) of $G$ is the {\em edge domination number} (resp. {\em total edge domination number}) of $G$, denoted by $\gamma^{'}(G)$ (resp. $\gamma_t^{'}(G)$). In the present paper, we prove that the total edge domination problem is NP-complete for bipartite graphs with maximum degree 3. We also design a linear-time algorithm for solving this problem for trees. Finally, for a graph $G$, we give the inequality $\gamma^{'}(G)\leqslant \gamma^{'}_{t}(G)\leqslant 2\gamma^{'}(G)$ and characterize the trees $T$ which obtain the upper or lower bounds in the inequality., Comment: 24 pages, 15 figures, 17 references

A graph $G$ is a cocomparability graph if there exists an acyclic transitive orientation of the edges of its complement graph $\overline{G}$. LBFS$^{+}$ is a variant of the generic Lexicographic Breadth First Search (LBFS), which uses a specific tie-breaking mechanism. Starting with some ordering $\sigma_{0}$ of $G$, let $\{\sigma_{i}\}_{i\geq 1}$ be the sequence of orderings such that $\sigma_{i}=$LBFS$^{+}(G, \sigma_{i-1})$. The LexCycle($G$) is defined as the maximum length of a cycle of vertex orderings of $G$ obtained via such a sequence of LBFS$^{+}$ sweeps. Dusart and Habib conjectured in 2017 that LexCycle($G$)=2 if $G$ is a cocomparability graph and proved it holds for interval graphs. In this paper, we show that LexCycle($G$)=2 if $G$ is a $\overline{P_{2}\cup P_{3}}$-free cocomparability graph, where a $\overline{P_{2}\cup P_{3}}$ is the graph whose complement is the disjoint union of $P_{2}$ and $P_{3}$. As corollaries, it's applicable for diamond-free cocomparability graphs, cocomparability graphs with girth at least 4, as well as interval graphs., Comment: 11 pages, 9 figures