% Template for Electronic Journal of Graph Theory and Applications
% This file must be in the same folder as EJGTAart.sty and EJGTAhead.jpg

\documentclass[12pt]{elsarticle}
\usepackage{tikz}
\usepackage[left=1in,right=1in, top=1.2in,bottom=1.2in]{geometry}
\usepackage{EJGTAart}
\usepackage{times}
\usepackage{amssymb,amsthm,latexsym,amsmath,epsfig,pgf}

% Set the volume if you know.
\volume{{\bf x} (x)}

% Set the starting page
\firstpage{1}

% Title (or short title) and author name for the header
\runauth{
Title of the manuscript
\hspace{2ex} $\arrowvert$\hspace{2ex}
Edy Tri Baskoro et al.}


% Put new theorem or any other settings for your document here
\newtheorem{theorem}{Theorem}[section]
\newtheorem*{theorem A}{Theorem A}
\newtheorem*{theorem B}{N\"olker's Theorem}
\newtheorem{lemma}{Lemma}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{definition}{Definition}[section]
\newtheorem{problem}{Problem}
\newtheorem*{question}{Question}
\newtheorem {conjecture}{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}{Remark}[section]
\theoremstyle{remark}
\newtheorem{remarks}{Remarks}
\begin{document}

\begin{frontmatter}
% Write your paper title here
\papertitle{Clique Roots of $K_{4}$ - Free Chordal Graphs}

%% use optional labels to link authors explicitly to addresses. The label may be more than one, use comma to separate

%\author[label1,label]{Edy Tri Baskoro${}^1$}

\author[label1]{Hossein Teimoori Faal}
%\author[label2]{Joe Ryan}
%\author[label3]{Kiki A. Sugeng}

\address[label1]{\small 
Department of Mathematics and Computer Science,\\
Allameh Tabataba'i University,\\
Tehran, Iran
%\address[label2]{School of Electrical Engineering and Computer Science,
%The University of Newcatle, Australia}
%\address[label3]{Departments of Mathematics,
%University of Indonesia,
%Depok - Indonesia

\vspace*{2.5ex} 
 {\normalfont 
 hossein.teimoori@gmail.com
 }
 }

\begin{abstract}
The clique polynomial $C(G,x)$ of a finite, simple and undirected graph
$G=(V,E)$ is defined as the ordinary generating function of the number 
of complete subgraphs 
of $G$. A real root of $C(G,x)$ is called a clique root of the graph 
$G$. Hajiabolhasan and Mehrabadi showed that 
every simple graph $G$ has at least a clique  
root in the interval 
$[-1,0)$. Moreover, they showed that the class of triangle-free
graphs has only clique roots. In this paper, we extend their 
result by showing that the class of $K_4$-free chordal 
graphs has also only clique roots. In particular, we show that this class has always a clique root $-1$. 
We conclude our paper
with some interesting open questions and conjectures.  


\let\thefootnote\relax\footnotetext{Received: xx xxxxx 20xx,\quad
  Accepted: xx xxxxx 20xx.\\[3ex]
  }
  
\end{abstract}

\begin{keyword}
% Separate keyword by \sep
Clique Polynomial \sep Clique Root \sep Chordal Graph \sep 
Clique Decomposition

% Write the classification number
Mathematics Subject Classification : 05C31, 05C69, 30C15

\end{keyword}

\end{frontmatter}

%% Main text
\section{Introduction and Motivation}
Throughout this paper graphs are finite, simple and undirected. 
For the terminology and notations which are not defined here, 
we refer the readers to the book 
$\cite{BondMurty(1976)}$.
For a given graph $G= (V, E)$, a complete subgraph of $G$ on $k$ vertices is called 
a $k$-\emph{clique}. For a subset $U \subseteq V(G)$, the subgraph induced on $U$ will be denoted
by $G[U]$. We recall that an edge which joins two vertices of a cycle but is not itself an edge of the cycle is called
a \emph{chord} of the cycle. A graph
is 
\emph{chordal} 
if each cycle of length at least four has a chord. We also recall that
the \emph{clique polynomial} $\cite{HajiMehrabadi(1998)}$ of the graph $G$, denote it by 
$C(G,x)$ is defined, as follows
%\begin{defn}
\begin{equation}
C(G,x):= 1 + \sum_{\emptyset \neq U \subseteq V(G):G[U]~is~a~clique}x^{\vert U\vert}, 
\end{equation} 
%\end{defn}
or equivalently 
\begin{equation}
C(G,x):= 1 + \sum_{k=1}^{\omega(G)} c_{k}(G), 
\end{equation}
in which $c_{k}(G)$ is the number of 
$k$-cliques in $G$ and $\omega(G)$ is the size of 
the largest clique of $G$. 
\\ 
Hajiabolhasan and Mehrabadi $\cite{HajiMehrabadi(1998)}$ showed that the
clique polynomial of every simple graph has always a real root
in the interval $[-1,0)$. 
We will call it the \emph{clique root} of $G$. 
They also 
showed that the class of triangle - free graphs has 
only clique roots. 
\\ 
Polynomials with only real roots arise
often in \emph{graph theory}
and other branches of mathematics. Such Polynomials with \emph{positive}
coefficients have attracted the attention of many researchers because of their 
implication on \emph{unimodality} and \emph{log-concavity}.  
%Proving that a particular class of graph polynomials has 
%only real roots has attracted the attention of many researchers working 
%in the area of algebraic graph theory, in recent years. This is partly because of the 
%several interesting properties of polynomials with only real roots 
%like being \emph{unimodal}. 
\\
Our main goal here is to contribute in this active line of research by extending the above result for the class of 
$K_4$ - free chordal graphs. More precisely, we will prove 
the following.  
\begin{theorem}\label{keythm1}
%[All Clique Roots Property For $K_4$ - free chordal graphs]
The class of $K_4$ - free connected chordal graphs has only clique roots. In particular, this class have always a clique root $-1$. 
\end{theorem}
We will also give the following immediate corollary of the above theorem, which is indeed a new algebraic proof of 
Turan's graph theorem for planar $K_{4}$ - free graphs.  
\begin{corollary}\label{keycor1}
If $G$ is a $K_{4}$ - free 
connected graph 
with $n$ vertices and $m$ edges, then we have
\begin{equation}
m \leq \frac{n^2}{3}.\nonumber 
\end{equation}
\end{corollary}
\section{Chordal Graphs and Clique Polynomials}
In this section, we investigate the important class of \emph{chordal graphs}. This class of graphs 
is very important in computer science, specially from the computational complexity view point. Many hard 
problems in general graphs have easy solutions in the class of chordal graphs. As we will see, the 
clique polynomial of chordal graphs can give us important insights into the structure of these graphs. 
\begin{definition}
A graph is \emph{chordal} if every cycle of length greater than three has a chord. 
A vertex of a graph is \emph{simplicial} if its neighbors induces a 
clique in the graph. 
\end{definition}
One of the important properties of a chordal graph is that it has always a \emph{clique decomposition}. For the sake completeness, here 
we quickly review the idea of decomposing a chordal graph into cliques. For detailed information, one can refer to $\cite{Tarjan1985}$. 
\begin{definition}
For given graphs $G_{1}$ and $G_{2}$, we say that a graph $G$ arises from $G_{1}$ and $G_{2}$ \emph{by pasting along} $S$ 
if we have $G_{1}\cup G_{2}= G$ and $G_{1} \cap G_{2} = S$. In this case, the graphs $G_{i}$ are called the 
\emph{simplicial summands} of $G$.  
\end{definition}    
\begin{remark}
From the above definition, it is clear that a graph is chordal 
if it can be constructed recursively by pasting complete graphs along cliques. 
It is not hard to see that this process is independent of the order in which complete graphs
paste to each other. Indeed, this recursive construction gives us a clique decomposition of chordal 
graphs which is essential to obtain their clique polynomials. 
\end{remark}
For simplicity of arguments, we use the notation 
$G_{1}\cup_{S} G_{2}$ whenever $G_{1}$ and $G_{2}$
are pasted along $S$. The following lemma is key to 
obtain an explicit formula for the clique polynomial 
of chordal graphs. The proof is straight forward 
application of the \emph{inclusion-exclusion principle}
and left to the reader as a simple exercise.    
\begin{proposition}
Let $G_1$ and $G_2$ be two simple graphs and 
$G = G_{1}\cup_{Q} G_{2}$ be their pasting along an
$i$ - clique $Q$. Then, we have 
\begin{equation}\label{keypast1}
C(G,x)
=
C(G_{1},x) + C(G_{2},x) - (x+1)^{i}, \hspace{1cm}
(i \geq 1).
\end{equation} 

\end{proposition}
By the successive application of the formula
(\ref{keypast1})
and the 
recursive construction of chordal graphs, we can 
obtain the following explicit 
formula for the clique polynomial of chordal graphs. 
\begin{theorem}
Let $G$ be a chordal graph defined as a pasting 
of the complete graphs 
$\{G_{i}\}^{r}_{i=1}$ of sizes $n_{i}$'s, respectively.
That is, 
$
G = 
G_{1}\cup_{Q_{1}} G_{2} \cup_{Q_{2}} \cdots
\cup_{Q_{r-1}} G_{r},
$ 
where 
$\{Q_{j}\}^{r-1}_{j=1}$ are cliques of sizes
$l_{j}$'s, respectively. Then, we have
\begin{equation}
C(G,x)
=
\sum_{i=1}^{r}(x+1)^{n_i} - 
\sum_{j=1}^{r-1}(x+1)^{l_j}. 
\end{equation}
  
\end{theorem}
As an immediate consequence of 
the above theorem, we have the following 
interesting result. 
\begin{corollary}\label{cormain1}
Every chordal graph $G$ without isolated vertices 
has always a clique root $-1$
.
The multiplicity of this root is equal to the 
size of the smallest clique in the pasting process of the 
recursive construction of $G$.   
\end{corollary}




















\section{Proofs of the Main Results}
Here, we first give a proof of
the following proposition which is  
a weaker version of Theorem  
\ref{keythm1}.
From now on, we will assume that our graphs are connected. 
\begin{proposition}\label{keyprop1}
The class of 
$K_{4}$ - free planar chordal graphs 
has only clique roots. In particular, $-1$ is always a clique root. 
\end{proposition}




\begin{proof}
For a given $K_{4}$ - free planar graph $G$, by \emph{Euler Formula}, we have
\begin{equation}\label{equt1}
n - m + f = 2,
\end{equation}
where $n$, $m$ and $f$ are the number of vertices, edges and faces of a 
\emph{planar embedding} of $G$, respectively. Moreover, if $G$ is a chordal 
graph, then we observe that 
\begin{equation}\label{equt2}
f = t + 1,
\end{equation}
where $t$ is the number of triangles ( triangular faces ) of $G$. Hence, form 
(\ref{equt1}) and (\ref{equt2}), we conclude that
$$
n - m +  t = 1, 
$$
or equivalently
\begin{equation}
1 - n + m - t = 0.
\end{equation}
By last identity and considering the fact that the clique 
polynomial of a $K_{4}$ - free graph G is 
$C(G,x) = 1 + n x + m x^2 + t x^3$, we get 
$$
C(G,-1) = 1-n + m - t = 0.
$$
That is, every 
$K_{4}$ - free planar chordal graph $G$ has always 
$-1$ as 
a clique root. 
Therefore, we obtain the following multiplicative 
decomposition of $C(G,x)$
\begin{equation}
C(G,x)= (1 + x)( 1 + (n-1)x + (m - n +1 )x^2).
\end{equation}
The 
final step of the proof is to show that the 
quadratic 
polynomial:
\begin{equation}
Q(G,x) = 1 + (n-1)x + (m - n +1 )x^2,
\end{equation}
has always a real root. 
To this end, we actually prove that 
$Q(G,x)$ is a clique polynomial of a 
\emph{triangle-free} graph 
$\tilde{G}$ which can be obtained from 
the original graph $G$ based on the 
idea of a \emph{rooted spanning tree} of $G$. 
\\
For a given $K_{4}$ - free chordal graph $G$, 
pick up an arbitrary vertex $v \in V(G)$. 
Now, we construct a spanning tree of 
$G$ rooted at the vertex $v$. We will denote it by
$T_{G}$. Clearly, this tree has $n$ vertices and 
$n-1$ edges. 
Now in the graph $G$, delete all $n-1$ edges 
of the tree $T_{G}$ and call the resulting graph 
$\hat{G}$. This graph has clearly $n$ 
vertices and $m-(n-1)$ edges. By the construction, it is clear that 
 $\hat{G}$ is a triangle - free graph
and $v$ is an isolated vertex of $\hat{G}$.   
Thus, the triangle-free graph 
$\tilde{G}$ 
obtained from $\hat{G}$ by deleting the vertex 
$v$ has $n-1$ vertices and $m-n+1$ edges, as required. 



\end{proof}
\newpage 
\begin{remark}
The following figure illustrates the process of 
obtaining the triangle-free graph 
$\tilde{G}$ from the original graph $G$
for a sample $K_{4}$-free connected chordal graph $G$.


\begin{center}
\begin{tikzpicture}
\draw (0,0) -- (0.5,1) -- (1,0) -- (0,0);
\draw (0,0) -- (0.5,-1) -- (1,0) -- (1.5,1) 
-- (0.5,1);
\draw (1,0) -- (1.5,-1) -- (0.5,-1); 

\draw [fill] (0,0) circle [radius=0.07];
\draw [fill] (0.5,1) circle [radius=0.07];
\draw [fill] (1,0) circle [radius=0.07];
\draw [fill] (0.5,-1) circle [radius=0.07];
\draw [fill] (1.5,-1) circle [radius=0.07];
\draw [fill] (1.5,1) circle [radius=0.07];

\node [left] at (0,0) {$v$};
\node [left] at (2.3,0) {$\Rightarrow$};
\node [left] at (-0.5,0.35) {$G:$};


\draw [red] (3.5,0) -- (4,1) ;
\draw [red] (3.5,0) -- (4.5,0) ;
\draw [red] (3.5,0) -- (4,-1) ;
\draw [red] (4,1) -- (5,1) ; 
\draw [red] (4.5,0) -- (5,-1) ;

\draw [fill] (3.5,0) circle [radius=0.07];
\draw [fill] (4,1) circle [radius=0.07];
\draw [fill] (4.5,0) circle [radius=0.07];
\draw [fill] (4,-1) circle [radius=0.07];
\draw [fill] (5,-1) circle [radius=0.07];
\draw [fill] (5,1) circle [radius=0.07];

\node [left] at (3.5,0) {$v$};
\node [left] at (5.7,0) {$\Rightarrow$};
\node [left] at (3.0,0.35) {$T_{G}:$};




\draw [green] (7.5,1) -- (8,0) ;
\draw [green] (8,0) -- (8.5,1) ;
\draw [green] (8,0) -- (7.5,-1) ;
\draw [green] (7.5,-1) -- (8.5,-1) ;

\draw [fill] (7,0) circle [radius=0.07];
\draw [fill] (7.5,1) circle [radius=0.07];
\draw [fill] (8,0) circle [radius=0.07];
\draw [fill] (7.5,-1) circle [radius=0.07];
\draw [fill] (8.5,-1) circle [radius=0.07];
\draw [fill] (8.5,1) circle [radius=0.07];

\node [left] at (7,0) {$v$};
\node [left] at (9,0) {$\Rightarrow$};
\node [left] at (6.3,0.35) {$\hat{G}:$};



\draw [blue] (10,1) -- (10.5,0) ;
\draw [blue] (10.5,0) -- (11,1) ;
\draw [blue] (10.5,0) -- (10,-1) ;
\draw [blue] (10,-1) -- (11,-1) ;

%\draw [fill] (7,0) circle [radius=0.07];
\draw [fill] (10,1) circle [radius=0.07];
\draw [fill] (10.5,0) circle [radius=0.07];
\draw [fill] (10,-1) circle [radius=0.07];
\draw [fill] (11,-1) circle [radius=0.07];
\draw [fill] (11,1) circle [radius=0.07];


\node [left] at (9.7,0.35) {$\tilde{G}:$};










\end{tikzpicture}

\end{center}
\begin{center}
\text{
Fig1. The construction of the triangle-free graph $\tilde{G}$
}
\end{center}






\end{remark}
Now, we are ready to give a proof of our main 
theorem. 
\begin{proof}[Proof of Theorem \ref{keythm1}]
We first note that by Corollary 
\ref{cormain1}, 
every connected chordal graph has always a clique root 
$-1$. Now, the rest of the proof is similar to  
the proof of Proposition \ref{keyprop1}. 
\end{proof}



Next we give an algebraic proof of 
the \emph{Turan's Graph Theorem} $\cite{Aigner}$
for $K_{4}$ - free graphs which is indeed 
Corollary \ref{keycor1}. 

\begin{proof}[Proof of Corollary \ref{keycor1}]
We first note that since we want to prove an upper 
bound for the maximum possible number of edges, without 
loss of generality we can assume that the graph $G$ is 
chordal. 
\\
By the proof of Theorem \ref{keythm1}, we already 
know that if $G$ is a given 
$K_{4}$ - free chordal graph with $n$ vertices and $m$ edges, 
then the following \emph{quadratic} equation
$$
Q(G,x) = 1 + (n-1)x + (m - n +1 )x^2,
$$
has only real zeros. Hence, it's \emph{discriminant} is 
nonnegative and therefore we have the following inequality:
$$
(n-1)^{2} - 4(m - n +1) \geq 0,
$$
which is equivalent to 
\begin{equation}\label{ineq1}
m \leq \left(\frac{n + 1}{2}\right)^{2} - 1.
\end{equation} 
On the other hand, we have the inequality 
\begin{equation}\label{ineq2} 
\left(\frac{n + 1}{2}\right)^{2} - 1 \leq \frac{n^{2}}{3},
\end{equation}
which is equivalent to the obvious inequality $ (n-3)^{2} \geq 0$. 
Thus, the inequalities (\ref{ineq1}) and (\ref{ineq2}) 
immediately imply the Turan's inequality 
for $K_{4}$ - free graphs.   
\end{proof} 










\section{Open problems and questions}



We already showed that the class of $K_{4}$ - free 
connected chordal graphs has only 
clique roots. Now, one might ask whether the class of 
$K_{5}$ - free connected chordal 
graphs has the same property or not. 
Unfortunately, this is not true in general. For example, 
the connected  
graph $K_{4}^{+}$ ( a complete graph $K_{4}$ plus one edge ) 
has only two clique roots. Indeed, we have 
$$
C(K_{4}^{+}) = 1 + 5x + 7x^2 + 4x^3 + x^4 = (1 + x)(1+ 4x + 3x^2 + x^3). 
$$
Since the cubic polynomial $\phi(x) = 1+ 4x + 3x^2 + x^3$ has the first derivative $\phi(x)' = 3(x+1)^2 + 1$ 
which is always \emph{positive}, by the first derivative criteria,  
$\phi(x) = 1+ 4x + 3x^2 + x^3$ has exactly \emph{one} real root. 
Thus, we come up with the following first open question. 
\\
\begin{problem}
Which subclasses of $K_{5}$ - free chordal 
graphs have only clique roots? 
\end{problem} 
Recall that the class of $3$ - trees 
are those graphs 
which can be constructed \emph{recursively} by 
starting with a complete graph $K_{4}$, and then 
\emph{repeatedly} adding vertices in such a way that 
each added vertex has exactly \emph{three} neighbors 
that form a clique (triangle). 
\\
By the above definition, it is not hard to see that the class of 
$3$ - tress is a subclass of 
$K_{5}$ - free chordal 
graphs. Next, we come up with the following conjecture.  
\begin{conjecture}

The class of $3$ - trees has only clique roots.
\end{conjecture}
Considering the fact that any connected chordal graph has 
a clique root $-1$ and the recursive definition of 
of chordal graphs, we made the following stronger conjecture. 
\begin{conjecture}
The class of $K_{5}$ - free connected chordal 
graphs with a clique root $-1$ of multiplicity $2$ 
has only clique roots.
\end{conjecture}
Considering the above discussions, we also come 
up with the following open question. 
\begin{problem}
Which subclasses of $K_{\omega+3}$ - free connected   
graphs ($\omega >0$) have only clique roots? 
\end{problem}
We call an $i$-clique an \emph{isolated clique}
if the intersection of all neighborhoods 
of it's vertices is an \emph{empty} set. In particular,
an isolated $1$-clique is called an isolated vertex. 
\\ 
The interesting point is that we strongly
believe that the following much stronger conjecture 
is true. 

\begin{conjecture}
The class of $K_{\omega+3}$ - free graphs
without isolated $\omega$ - cliques
has only clique roots.
\end{conjecture} 






%\section*{Acknowledgement} 
%Write support, acknowledgment, dedicatory, and grants here.

\section*{References} 
\begin{thebibliography}{99}

\bibitem{BondMurty(1976)} 
J. A. Bondy and U. S. R. Murty, 
Graph theory with applications, 
\textit{American Elsevier Publishing Co. Inc., New York} 
 (1976).



\bibitem{HajiMehrabadi(1998)} 
H. Hajiabolhassan and M. L. Mehrabadi, 
On clique polynomials, 
\textit{Australasian Journal of Combinatorics.} 
\textbf{18} (1998), 313--316. 

\bibitem{Tarjan1985} 
R. E. Tarjan, 
Decomposition by clique separators,
\textit{Discrete Mathematics.}
\textbf{55} (1985), 221--232. 


\bibitem{Aigner} 
M. Aigner, 
Tur\'{a}n's graph theorem, 
\textit{ Journal of American Mathematical Monthly.} 
\textbf{6} (1995), 808-816.

\end{thebibliography}

\end{document}

%%
%% End of file `ecrc-template.tex'. 