# A Rotating Proposer Mechanism for Team Formation

Jian Lou1, Chen Hajaj2, and Yevgeniy Vorobeychik4
1Amazon, 2Ariel University, 4Washington University in St. Louis

##  1 The Rotating Proposer Mechanism

A _rotating proposer mechanism_ is a way to operationalize _sequential
proposer games_ in mechanism design for team formation. formally define a
_team formation mechanism_. A _team formation mechanism_ $M$ maps every
preference profile $\succ$ to a partition $\pi$ of the set of players, i.e.
$\pi=M(\succ)$. Our goal is to exhibit such a mechanism, and analyze its
properties. The mechanism, termed Rotating Proposer Mechanism (RPM),
implements the subgame perfect Nash equilibrium of the sequential proposer
game with each proposer able to make an offer to each possible team, in which
all proposals are accepted (thus, only a single offer is actually made). In
this equilibrium, whenever it’s a player $i$’s turn to propose, $i$ makes a
proposal to her most preferred team among those that would be accepted.

For any profile, if all players report their preferences truthfully,
equilibrium outcomes of the game have a number of good properties which are
thereby inhereted by RPM. Of particular note is that RPM is individually
rational, Pareto optimal, and implements iterated matching of soulmates (IMS)
(see [6]). However, it is also immediate from known results that the RPM
mechanism is not in general strategyproof (this would conflict with individual
rationality and implementing IMS [6]).

The loss of incentive compatibility seems problematic. However, one side-
effect of RPM implementing IMS is that RPM is strongly incentive
compatible111More precisely, truth telling is a strong ex post Nash
equilibrium. and yields a unique core team structure on a restricted class of
preference domains for which IMS always matches all players [6]. As an
example, these domains include other well-known restrictions on preferences,
such as top coalition [3] and common ranking [5] properties.

This, however, would seem to limit its practical consideration, as such
restrictions can rarely be guaranteed or verified. Moreover, we wish to make
stronger efficiency claims than Pareto optimality, and also view fairness as
an important criterion. For the former, we are particularly interested in
_utilitarian social welfare_ , a much stronger criterion than Pareto
efficiency. We will also consider several notions of fairness discussed below.
While we cannot make strong theoretical guarantees about these for broad
realistic preference domains, we consider such properties empirically.

While RPM is a rather intuitive mechanism, it is quite challenging to
implement the associated subgame perfect Nash equilibrium. In particular, the
size of the backward induction search tree is
$O(2^{\sum_{i=1}^{n}|\mathcal{T}_{i}|})$. Even in the roommate problem, in
which the size of teams is at most two, computing SPNE is $O({2^{n}}^{2})$. We
address this challenge in three ways: (1) preprocessing and pruning to reduce
the search space, (2) approximation for the roommate problem, and (3) a
general heuristic implementation.

###  1.1 Preprocessing and Pruning

One of the central properties of RPM is that it implements iterative matching
of soulmates. In fact, it does so in every subgame in the backwards induction
process. Now, observe that computing the subset of teams produced through IMS
is $O(n^{3})$ in general, and $O(n^{2})$ for the roommate problem, and is
typically much faster in practice. We therefore use it as a preprocessing step
both initially (reducing the number of players we need to consider in
backwards induction) and in each subgame of the backwards induction search
tree (thereby pruning irrelevant subtrees).

Because IMS preprocessing is computationally efficient, it is always applied
before any of the approximate/heuristic versions of RPM below, with the direct
consequence that even these approximate versions implement IMS.

We show the computational value of IMS in preprocessing and pruning using
synthetic preference profiles based on the generative scale-free model.

Figure 1: Time consumed ratio (with IMS/without IMS) for RPM on scale-free
networks

Figure 1 shows the ratio of time consumed by RPM with IMS to that without
IMS.222The simulations describes in this section were run on a 2.6 GHz Intel
Core i5 Mac machine with 8 GB RAM. In all cases, we see a clear trend that
using IMS in preprocessing and pruning has increasing importance with
increased problem size.

###  1.2 Approximate RPM for the Roommate Problem

Using IMS for preprocessing and pruning does not sufficiently speed up RPM
computation in large-scale problem instances. Thus, we next developed a
parametric approximation of RPM that allows us to explicitly trade off
computational time against approximation quality. We leverage the observation
that the primary computational challenge of applying RPM to the roommate
problem is determining whether a proposal is to be accepted or rejected. If we
are to make this decision without exploring the full game subtree associated
with it, considerable time can be saved. Our approach is to use a heuristic to
evaluate the “likely” opportunity of getting a better teammate in later
stages: if this heuristic value is very low, the offer is accepted; if it is
very high, the offer is rejected; and we explore the full subgame in the
balance of instances.

More precisely, consider an arbitrary offer from player $i$ to another player
$j$. Given the subgame of the corresponding RPM, let $\mathcal{U}_{j}(i)$
denote the set of feasible teammates that $j$ prefers to $i$, and let
$\mathcal{U}_{j}(j)$ be the set of feasible teammates who $j$ prefers to be
alone. We can use these to heuristically compute the likelihood $R_{j}(i)$
that $j$ can find a better teammate than the proposer $i$:

$\displaystyle R_{j}(i)=$
$\displaystyle\frac{|\mathcal{U}_{j}(i)|}{|\mathcal{U}_{j}(j)|}\cdot\frac{1}{|\mathcal{U}_{j}(i)|}\sum_{k\in\mathcal{U}_{j}(i)}\left(1-\frac{|\mathcal{U}_{k}(j)|}{|\mathcal{U}_{k}(k)|}\right)=$
$\displaystyle\frac{1}{|\mathcal{U}_{j}(j)|}\sum_{k\in\mathcal{U}_{j}(i)}\left(1-\frac{|\mathcal{U}_{k}(j)|}{|\mathcal{U}_{k}(k)|}\right)$
(1)

Intuitively, we first compute the proportion of feasible teammates that $j$
prefers to $i$. Then, for each such teammate $k$, we extract the proportion of
feasible teammates who are not more preferred by $k$ than the receiver $j$.
Our heuristic then uses an exogenously specified threshold, $\alpha$,
($0\leq\alpha\leq 0.5$) as follows. If $R_{j}(i)\leq\alpha$, player $j$
accepts the proposal, while if $R_{j}(i)\geq 1-\alpha$, the proposal is
rejected. In the remaining cases, our heuristic proceeds with evaluating the
subgame at the associated decision node. Consequently, when $\alpha=0$, it is
equivalent to the full backwards induction procedure, and computes the exact
RPM. Note that for any $\alpha$, this approximate RPM preserves IR, and we
also maintain IMS by running it as a preprocessing step.

The parameter $\alpha$ of our approximation method for RPM in the roommate
problem allows us to directly evaluate the trade-off between running time and
quality of approximation; small $\alpha$ will lead to less aggressive use of
the acceptance/rejection heuristic, with most evaluations involving actual
subgame search, while large $\alpha$ yields an increasingly heuristic approach
for computing RPM, with few subgames fully explored.

(a) Time consumed ratio

(b) average proportion of same teams

Figure 2: Time consumed and average proportion of same teams

Figure 2(a) depicts the fraction of time consumed by RPM with different values
of $\alpha$ compared to exact RPM (when $\alpha=0$) on scale-free networks
($m=3$). Based on this figure, even a comparatively small value of $\alpha$
dramatically decreases computation time.

Figure 2(b) compares similarity of the final team partition when using the
heuristic compared to the exact RPM. Notice that even for high values of
$\alpha$, there is a significant overlap between the outcomes selected by RPM
with and without the heuristic. We note that $\alpha=0.1$ appears to trade off
approximation quality and running time particularly well: for comparatively
sparse networks (i.e., $m=2$) it yields over $99\%$ overlap with exact RPM
(this proportion is only slightly worse for denser networks), at a small
fraction of the running time. Henceforth, we use $\alpha=0.1$ when referring
to the approximate RPM in the reminder of this section.

###  1.3 Heuristic Rotating Proposer Mechanism (HRPM)

Unlike the roommate problem, general team formation problems have another
source of computational complexity: the need to iterate through the
combinatorial set of potential teams to propose to. Moreover, evaluating
acceptance and rejection becomes considerably more challenging. We therefore
develop a more general heuristic which scales far better than the approaches
above, but no longer has the exact RPM as a special case. We term the
resulting approximate mechanism _Heuristic Rotating Proposer Mechanism (HRPM)_
, and it assumes that the sole constraint on teams is their cardinality and
that preferences can be represented by an additively separable utility
function [3]. With the latter assumptions, we allow preferences over teams to
be represented simply as preference orders over potential teammates, avoiding
the combinatorial explosion in the size of the preference representation.

In HRPM, each proposer $i$ attempts to add a single member to their team at a
time in the order of preferences over players. If the potential teammate $j$
accepts $i$’s proposal, $j$ is added to $i$’s team, and $i$ proposes to the
next prospective teammate until either the team size constraint is reached, or
no one else who $i$ prefers to being alone is willing to join the team. Player
$j$’s decision to accept or reject $i$’s proposal is based on calculating
$R_{j}(l)$ for each member $l$ of $i$’s current team $T$ using Equation 1, and
then computing the average for the entire team,
$R_{j}(T)=\frac{1}{|T|}\sum_{l\in T}R_{j}(l)$ (see Algorithm 1 for the precise
description of HRPM). We then use an exogenously specified threshold
$\beta\in[0,1]$, where $j$ accepts if $R_{j}(T)\leq\beta$ and rejects
otherwise. The advantage of HRPM is that the team partition can be found in
$O(\omega n^{2})$, where $\omega$ is the maximum team size. The disadvantage,
of course, is that it only heuristically implements RPM. Crucially, it does
preserve IR, and IMS is implemented as a preprocessing step.

Algorithm 1 Heuristic Rotating Proposer Mechanism (HRPM)

input: $(N,\succeq,O)$, $\omega$, $\beta$
return: Team formation outcome $\pi$

1:$\pi=\emptyset$

2:while $O$ is non-empty do

3: $i\leftarrow$ the first player in $O$

4: $\pi_{i}\leftarrow\\{i\\}$

5: while $|\pi_{i}|<\omega$ do

6: if $\succeq_{i}$ is empty or the first player in $\succeq_{i}$ is $i$ then

7: $O\leftarrow O\backslash\\{i\\}$

8: break

9: player $i$ proposes to the first player $j$ in $\succeq_{i}$

10:
$R_{j}(\pi_{i})=\frac{1}{|\pi_{i}|}\sum_{l\in\pi_{i}}\frac{1}{|\mathcal{U}_{j}(j)|}\sum_{k\in\mathcal{U}_{j}(i)}\left(1-\frac{|\mathcal{U}_{k}(j)|}{|\mathcal{U}_{k}(k)|}\right)$

11: if $R_{j}(\pi_{i})\leq\beta$ then $\triangleright$ player $j$ accepts the
proposal

12: $\pi_{i}\leftarrow\pi_{i}\cup\\{j\\}$

13: remove $j$ from $O$ and $N$

14: remove $j$ from $\succeq_{k}$ for each player $k\in N$

15: remove $i$ from $O$, $N$ and $\succeq_{k}$ for each player $k\in N$

16:while $N$ is non-empty do $\triangleright$ add singletons into the outcome.

17: pick an arbitrary instance $i$ from $N$

18: remove $i$ from $O$ and $N$

19:return $\pi$

##  2 Properties of Exact and Approximate RPM

Over truthful preference reports, RPM inherits the properties of the game,
including IR, IMS, and Pareto efficiency. In general, however, these
properties conflict with incentive compatibility. Moreover, when it comes to
efficiency, Pareto optimality is a weak criterion and we would wish to know
how well a mechanism fairs in terms of stronger efficiency criteria, such as
utilitarian social welfare (with cardinal preferences). Fairness, too, is an
important consideration in matching, particularly when it comes to forming
teams. Next, we explore these issues using empirical tools.

###  2.1 Empirical Methodology

In our empirical assessments, we use both synthetic and real hedonic
preference data. In both cases, preferences were generated based on a social
network structure in which a player $i$ is represented as a node and the total
order over neighbors is then generated randomly. Non-neighbors represent
undesirable teammates ($i$ would prefer being alone to being teamed up with
them).

The networks used for our experiments were generated using the following
models:

  * •

Scale-free network: We adapt the Barabási-Albert model [1] to generate scale-
free networks. For each $(n,m)$, where $n$ is the number of players, $m$
denotes the density of the network, we generate $1,000$ instances of networks
and profiles.

  * •

Karate-Club Network [9]: This network represents an actual social network of
friendships between 34 members of a karate club at a US university, where
links correspond to neighbors. We generate $100$ preference profiles based on
the network.

Finally, we used a _Newfrat_ dataset [8] that contains $15$ matrices recording
weekly sociometric preference rankings from $17$ men attending the University
of Michigan. In order to quantitatively evaluate both the exact and
approximate variants of RPM, the ordinal preferences $\succ_{i}$ have to be
converted to cardinal ones $u_{i}(\cdot)$, upon which both mechanisms operate.
For this purpose, we introduce a _scoring function_ suggested by [4] to
measure a player’s utility. To compute a player $i$’s utility of player $j$ we
adopt _normalized Borda scoring function_ , defined as
$u_{i}(j)=g(r)=2(k-r+1)/k-1$, where $k$ is the number of $i$’s neighbors, and
$r\in\\{1,\ldots,k\\}$ is the rank of $j$ in $i$’s preference list. Without
loss of generality, for every player $i$ we set the utility of being a
singleton $u_{i}(i)=0$. We assume that the preferences of players are
additively separable [3], which means that a player $i$’s utility of a team
$T$ is $u_{i}(T)=\sum_{j\in T}u_{i}(j)$.

###  2.2 Incentive Compatibility

In spite of the known impossibility results, the fact that RPM is not
incentive compatible may be intuitively surprising, given that it implements
an equilibrium of the complete information game. To gain further intuition
into this, consider the following example.

######  Example 1.

Consider a roommate problem with 3 players having the following preferences:

$\begin{matrix}&1:&\\{1,2\\}&\succ_{1}&\\{1,3\\}&\succ_{1}&\\{1\\}\\\
&2:&\\{2,3\\}&\succ_{2}&\\{2,1\\}&\succ_{2}&\\{1\\}\\\
&3:&\\{3,1\\}&\succ_{3}&\\{3,2\\}&\succ_{3}&\\{1\\}\\\ &&&&&&\end{matrix}$

Suppose that the order in RPM is $O=(1,1,1,1,2,2,2,2,3,3,3,3)$. In the subgame
perfect Nash equilibrium of the corresponding RPG, 1 will propose to
$\\{1,2\\}$, $2$ will accept, and the resulting teams are
$\\{\\{1,2\\},\\{3\\}\\}$. This is because 2 is 1’s most preferred roommate,
and if 2 rejects, then 1 would offer to 3 who would accept (since they like 1
more than 2), and 2 would be left alone.

Now, if player 3 misreports preferences to claim that she prefers 2 to 1, then
2 and 3 are soulmates and would be matched, with the resulting outcome
$\\{\\{1\\},\\{2,3\\}\\}$. The latter outcome is clearly preferred by 3, and
consequently 3 has the incentive to lie.

Despite the general failure of incentive compatibility in RPM, we now explore
_empirically_ how frequently this failure actually occurs. We use the roommate
problem, as in this case the special structure of RPM allows us to use
Algorithm 2 to compute an upper bound on the number of players who could
possibly benefit by misreporting preferences. In applying the algorithm, we
use $\mathcal{T}_{i}$ to denote the set of feasible teammates (since teams are
of size at most 2).

At the high level, this algorithm considers all the players who have accepted
or rejected a proposal and checks whether reversing this decision improves
their outcomes. The following theorem shows that this method indeed finds the
upper bound on the number of untruthful players.

######  Theorem 1.

Algorithm 2 returns an upper bound on the number of players who can gain by
misreporting their preferences.

###### Proof.

We divide the players into _proposers_ and _receivers_. Proposers are those
who propose in RPM and were thus teamed up (including singleton teams).
Receivers accept or reject someone’s offer.

Algorithm 2 Computing Upper Bound of Untruthful Players

input: $(N,\succ,\mathcal{T},O)$ , teammate vector $teammate[]$ which results
from RPM
return: number of potential untruthful players $Sum$

1:$sum\leftarrow 0$

2:while $|O|\geq 2$ do

3: $proposer$ $\leftarrow$ the first player in $O$

4: $receiver$ $\leftarrow$ $teammate[proposer]$

5: for player $i\in\mathcal{T}_{proposer}$ do

6: if $i\succ_{proposer}receiver$ and $proposer\succ_{i}teammate[i]$ then

7: $sum\leftarrow sum+1$ $\triangleright$ $i$ is potentially untruthful

8: for player $j\in\mathcal{T}_{receiver}$ do

9: if $j\succ_{receiver}proposer$ and $receiver\succ_{j}teammate[j]$ then

10: $sum\leftarrow sum+1$ $\triangleright$ $receiver$ is potentially
untruthful

11: remove $proposer$ and $receiver$ from $N$, $O$ and $\mathcal{T}$

12:return $sum$

There are 4 possible cases:

  1. 1.

_A proposer $i$ untruthfully reveals her preference and remains a proposer._
As RPM implements subgame perfect Nash equilibrium in the corresponding
subgame, the proposer $i$ can match with the best roommate among those accept
her proposals by acting truthfully. Consequently, $i$ cannot improve by lying.

  2. 2.

_A receiver $j$ untruthfully reveals her preference and is still a receiver._
In this case, if $j$ has an incentive to lie, there has to be a proposer
$i^{\prime}$ who prefers $j$ to her teammate under RPM, while $j$ must prefer
$i^{\prime}$ to her teammate. Steps $4-7$ in Algorithm 2 count all such
instances.

  3. 3.

_A proposer $i$ untruthfully reveals her preference and becomes a receiver._
In this case, if $i$ has an incentive to untruthfully reveal her preference,
there has to be a proposer $i^{\prime}$ who prefers $i$ to their teammate
under RPM, and who $i$ also prefers to her teammate. Steps $4-7$ in Algorithm
2 count all such instances.

  4. 4.

_A receiver $j$ untruthfully reveals her preference and becomes a proposer._
In this case, if $j$ has an incentive to misreport her preference, there must
be a receiver $j^{\prime}$ who prefers $j$ to her teammate, while $j$ must
prefer $j^{\prime}$ to her teammate. Steps $8-10$ in Algorithm 2 count all
such instances.

∎

This upper bound obtains for both the exact and approximate versions of RPM,
including HRPM. Next we evaluate the incentives to misreport preferences using
our RPM approximations in the context of the roommate problem.

Table 1: Average upper bound of untruthful players for (Approximate) RPM n | 20 | 30 | 40 | 50 | 60 | 70 | 80
---|---|---|---|---|---|---|---
$m=2$, $\alpha=0$ | 0.015% | 0.013% | 0.013% | 0.002% | 0.008% | 0.011% | 0.010%
$m=2$, $\alpha=0.1$ | 0.015% | 0.010% | 0.015% | 0.004% | 0.022% | 0.029% | 0.036%
$m=3$, $\alpha=0$ | 0.105% | 0.107% | 0.072% | 0.038% | 0.037% | 0.024% | 0.023%
$m=3$, $\alpha=0.1$ | 0.115% | 0.103% | 0.085% | 0.076% | 0.065% | 0.074% | 0.093%
Table 2: Lower bound of profiles where every player is truthful for (Approximate) RPM n | 20 | 30 | 40 | 50 | 60 | 70 | 80
---|---|---|---|---|---|---|---
$m=2$, $\alpha=0$ | 99.7% | 99.6% | 99.5% | 99.9% | 99.6% | 99.2% | 99.2%
$m=2$, $\alpha=0.1$ | 99.7% | 99.7% | 99.4% | 99.8% | 98.8% | 98.1% | 97.2%
$m=3$, $\alpha=0$ | 97.9% | 96.8% | 97.1% | 98.1% | 97.8% | 98.4% | 98.3%
$m=3$, $\alpha=0.1$ | 97.8% | 96.9% | 96.8% | 96.2% | 96.3% | 95.1% | 92.9%

Table 1 presents the upper bound on the number of players with an incentive to
lie, as a proportion of all players, on scale-free networks. We observe that
the upper bound is always below $0.2\%$, and is even lower when the networks
are sparse ($m=2$). On the Karate club data, we did not find any player with
an incentive to lie in test cases when we apply (Approximate) RPM. On the
Newfrat data, the upper bounds are less than $7\%$ and $0.4\%$ when we apply
RPM with and without heuristics, respectively. In addition, we also computed
the lower bound on the fraction of preference profiles where truth telling is
a Nash equilibrium (Table 2). We find that without the heuristic, when $m=2$
(sparse networks), RPM is incentive compatible in more than $99\%$ of the
profiles; and when $m=3$ (the networks are comparatively dense), RPM is
truthful at least $96\%$ of the time.

Table 3: Average upper bound of untruthful players for HRPM n | 20 | 30 | 40 | 50 | 60 | 70 | 80
---|---|---|---|---|---|---|---
$m=2$, $\beta=0.5$ | 1.44% | 1.77% | 1.71% | 2.00% | 2.09% | 2.16% | 2.06%
$m=2$, $\beta=0.6$ | 1.62% | 1.83% | 1.96% | 2.09% | 2.25% | 2.11% | 2.11%
$m=3$, $\beta=0.5$ | 2.99% | 3.36% | 3.76% | 3.90% | 4.18% | 4.02% | 4.33%
$m=3$, $\beta=0.6$ | 3.44% | 3.69% | 3.97% | 3.98% | 4.40% | 4.24% | 4.52%

Table 3 presents the upper bound on the number of untruthful players for HRPM
(still for the roommate problem). Even with this heuristic, we can see that
fewer than 5% of the players have any incentive to misreport preferences in
all cases.

###  2.3 Efficiency

In terms of social welfare, ex post Pareto optimality, satisfied by both
random serial dictatorship (RSD) [2] and RPM, is a very weak criterion.
Moreover, it is not necessarily satisfied by our approximations of RPM.
Conversion of ordinal to cardinal preferences allows us to empirically
consider _utilitarian social welfare_ , a much stronger criterion commonly
used in mechanism design with cardinal preferences.

We define utilitarian social welfare as $\frac{1}{|N|}\sum_{i\in
N}u_{i}(\pi_{i})$, where $\pi_{i}$ is the team that $i$ was assigned to by the
mechanism.

(a) scale-free networks

(b) Karate and Newfrat

Figure 3: Utilitarian social welfare for roommate problem

Figures 3(a) and 3(b) depict the average utilitarian social welfare for RSD
and RPM in the roommate problem on scale-free networks, Karate club networks,
and the Newfrat data. In all cases, RPM yields significantly higher social
welfare than RSD, with $15\%-20\%$ improvement in most cases. These results
are statistically significant ($p<0.01$). Furthermore, there is virtually no
difference between exact and approximate RPM.

(a) scale-free networks

(b) Karate and Newfrat

Figure 4: Utilitarian social welfare for trio-roommate problem

For the trio-roommate problem (in which the maximum size of team is 3), we
compare HRPM ($\beta=0.6$) with RSD on the same data sets. Figures 4(a) and
4(b) show that HRPM yields significantly higher social welfare than RSD in all
instances, and HPRM performs even better when the network is comparatively
dense ($m=3$ in the scale-free network). All results are statistically
significant ($p<0.01$).

###  2.4 Fairness

A number of measures of fairness exist in prior literature. One common
measure, envy-freeness, is too weak to use, especially for the roommates
problem: every player who is not matched with her most preferred other will
envy someone else. Indeed, because RPM matches soulmates—in contrast to RSD,
which does not—it already guarantees the fewest number of envious players in
the roommates problem. We consider two alternative measures that aim to
capture different and complementary aspects of fairness: the Gini coefficient,
representing the inequality among values of player utilities, and the
correlation between utility and rank in the random proposer order (i.e.,
Pearson correlation).

(a) scale-free network

(b) Karate and Newfrat

Figure 5: Gini coefficient for the roommate problem

The Gini coefficient measures the inequality of player’s utilities. It is
extracted based on the Lorenz curve [7].333The proportion of the total utility
of the players that is cumulatively earned by the bottom $x\%$ of the
population. A Gini coefficient of zero expresses perfect equality, where all
the players have the same utility, while a Gini coefficient of one expresses
maximal inequality among values (e.g., for a large number of players, where
one team is composed of soulmates and all the players are matched to their
least preferred team).

Correlation between utility and rank considers each random ranking of players
in $O$ used for both RSD and RPM, along with corresponding utilities
$u_{i}(\pi)$ of players for the partition $\pi$ generated by the mechanism,
and computes the correlation between these. It thereby captures the relative
advantage that someone has by being earlier (or later) in the order to propose
than others, and is a key cause of ex post inequity in RSD. We view the
correlation measure as perhaps the most meaningful criterion of fairness for
mechanisms based on random player rankings: for example, someone who is
extremely unpopular is likely to have lower utility than others, but that’s
likely to remain the case for any team formation mechanism with good
efficiency properties. On the other hand, this may be relatively invariant of
the ex post position that the player has in the order of proposers.

(a) scale-free network

(b) Karate and Newfrat

Figure 6: Pearson Correlation for the roommate problem

(a) scale-free networks

(b) Karate and Newfrat

Figure 7: Gini coefficient for the trio-roommate problem

(a) scale-free networks

(b) Karate and Newfrat

Figure 8: Pearson Correlation for the trio-roommate problem

Our experiments on the roommate problem show that RPM is significantly more
equitable than RSD on scale-free networks (Figures 5(a) and 6(a)), as well as
on the Karate club network and Newfrat dataset (Figures 5(b) and 6(b)). The
differences between exact and approximate RPM are negligible in most
instances.

In the trio-roommate problem, HRPM ($\beta=0.6$) is much more equitable than
RSD as shown in Figures 7 and 8. These results are statistically significant
($p<0.01$).

## References

  * [1] Réka Albert and Albert-László Barabási.  Statistical mechanics of complex networks.  Rev. Mod. Phys., 74:47–97, Jan 2002.
  * [2] Sophie Bade.  Serial dictatorship: The unique optimal allocation rule when information is endogenous.  Theoretical Economics, 10:385–410, 2015.
  * [3] Suryapratim Banerjee, Hideo Konishi, and Tayfun Sönmez.  Core in a simple coalition formation game.  Social Choice and Welfare, 18(1):135–153, January 2001.
  * [4] Sylvain Bouveret and Jérôme Lang.  A general elicitation-free protocol for allocating indivisible goods.  In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume One, IJCAI’11, pages 73–78. AAAI Press, 2011.
  * [5] J. Farrell and S. Scotchmer.  Partnerships.  Quarterly Journal of Economics, 103:279–297, 1988.
  * [6] Greg Leo, Jian Lou, Martin Van der Linden, Yevgeniy Vorobeychik, and Myrna Wooders.  Matching soulmates.  Journal of Public Economic Theory, 23(5):822–857, 2021.
  * [7] Max O Lorenz.  Methods of measuring the concentration of wealth.  Publications of the American statistical association, 9(70):209–219, 1905.
  * [8] P. Nordlie.  A longitudinal study of interpersonal attraction in a natural group setting.  PhD thesis, University of Michigan, 1958.
  * [9] W.W. Zachary.  An information flow model for conflict and fission in small groups.  Journal of Anthropological Research, 33:452–473, 1977.


# Extremal Chemical Graphs for the Arithmetic-Geometric Index

Alain Hertza,***Corresponding author<EMAIL_ADDRESS>, Sébastien
Bonteb, Gauvain Devillezb,c,
Valentin Dusollierb, Hadrien Mélotb, David Schindld
aDepartment of Mathematics and Industrial Engineering,
Polytechnique Montréal - Gerad, Montréal, Canada
bComputer Science Department - Algorithms Lab
University of Mons, Mons, Belgium
cFaculty of Mathematics and Physics
University of Ljubljana, Ljubljana, Slovenia
dHaute école de gestion de Genève
University of Applied Sciences Western Switzerland, Genève, Switzerland

###### Abstract

The arithmetic-geometric index is a newly proposed degree-based graph
invariant in mathematical chemistry. We give a sharp upper bound on the value
of this invariant for connected chemical graphs of given order and size and
characterize the connected chemical graphs that reach the bound. We also prove
that the removal of the constraint that extremal chemical graphs must be
connected does not allow to increase the upper bound.

##  1 Introduction

In mathematical chemistry, and more specifically in chemical graph theory,
topological indices are values that characterize a graph representing a
molecule. This value is correlated with some properties of said molecule. One
largely studied class of such indices is composed of degree-based invariants.
A well known example of these is the Randić index, proposed by Randić [14] in
1975. Following the interest in this index, many others were later introduced.
Of interest here is the _arithmetic-geometric index_ proposed in 2015 by
Shegehalli and Kanabur [17]. Let $G$ be a graph with edge set $E$ and let
$d_{u}$ and $d_{v}$ be the degrees of the endpoints of an edge $uv\in E$. The
arithmetic-geometric index $\texttt{AG}(G)$ of $G$, is defined as

$\texttt{AG}(G)=\sum_{uv\in E}\frac{d_{u}+d_{v}}{2\sqrt{d_{u}d_{v}}}.$

The summand in the above formula is the ratio between the arithmetic and
geometric means of $d_{u}$ and $d_{v}$. If we replace each summand by its
inverse, we obtain another graph invariant known as the geometric-arithmetic
index introduced in 2009 by Vukičević and Furtula [20] and studied for example
in [15, 2, 1, 5]. Several papers have focused on properties of the arithmetic-
geometric index. For example, Shegehalli and Kanabur [17, 18] give the value
of this index for some families of graphs. Lower bounds for graphs of fixed
size (i.e., number of edges) are provided in [16, 12, 19], while an upper
bound for graphs with fixed size and order (i.e., number of vertices) is
established in [19]. Upper bounds for graphs of fixed size and fixed minimum
and maximum degrees are given in [16, 11, 12]. The maximum value of the
arithmetic-geometric index of graphs of fixed order is known for unicyclic
graphs [21], bicyclic graphs [13], bipartite graphs and trees [19]. In
addition, Vujošević et al. [19] have characterized the chemical trees with
maximum arithmetic-geometric index value. The relationship between the
arithmetic-geometric index and other topological indices is studied, for
example in [4, 16, 11, 12, 8, 3, 9].

In this paper, we prove the following upper bound on the value of the
arithmetic index of a connected chemical graphs $G$ of order $n$ and size $m$:

$\texttt{AG}(G)\leq\frac{2n+5m}{6}+\left\\{\begin{array}[]{ll}0&\mbox{\emph{if}
}2m-n\equiv 0\bmod{3},\\\ \frac{3}{\sqrt{2}}-\frac{13}{6}&\mbox{\emph{if}
}2m-n\equiv 1\bmod{3},\\\ \frac{21}{4\sqrt{3}}-\frac{37}{12}&\mbox{\emph{if}
}2m-n\equiv 2\bmod{3}.\end{array}\right.$

We show that with the exception of 22 $(n,m)$ pairs, the bound is sharp, and
we characterize the connected chemical graphs of order $n$ and size $m\geq
n-1$ that reach the bound. We also prove that no better value can be obtained
by removing the constraint that the graph must be connected. Note that for
$m=n-1$, this gives a characterization of extremal chemical trees of fixed
order $n$. While such a characterization is given in [19], we show that their
result is not valid for 7 values of $n$.

In the next section we fix some notations, while Section 3 is devoted to
observations that will motivate our characterization of connected chemical
graphs with maximum arithmetic-geometric index value. Lemmas are proved in
Section 4 and then used in Section 5 to prove the main theorem.

##  2 Notations

For basic notions of graph theory that are not defined here, we refer to
Diestel [7]. Let $G=(V,E)$ be a simple undirected graph. The _order_ $n=|V|$
of $G$ is its number of vertices and the _size_ $m=|E|$ of $G$ is its number
of edges. We write $G\simeq H$ if $G$ and $H$ are isomorphic. The _degree_ of
$v$, denoted $d_{v}$ is the number of edges incident to $v$, and we say that
$v$ is _isolated_ if $d_{v}=0$.

A _chemical graph_ is a graph whose vertices have degree at most 4. The
arithmetic-geometric index $\texttt{AG}(G)$ of a graph $G$ can be seen as a
sum of costs on the edges of $G$. In particular, if we deal with chemical
graphs, there is a limited number of possible values for the costs since they
are computed from the degrees of the endpoints of the edges. Let
$c_{i,j}=\frac{i+j}{2\sqrt{ij}}$ be the cost of an edge with endpoints of
degree $i$ and $j$. The $4\times 4$ cost matrix $C_{\texttt{AG}}$ associated
with the arithmetic-geometric index of chemical graphs is

$C_{\texttt{AG}}=\begin{pmatrix}1&\frac{3}{2\sqrt{2}}&\frac{2}{\sqrt{3}}&\frac{5}{4}\\\\[5.16663pt]
\frac{3}{2\sqrt{2}}&1&\frac{5}{2\sqrt{6}}&\frac{3}{2\sqrt{2}}\\\\[5.16663pt]
\frac{2}{\sqrt{3}}&\frac{5}{2\sqrt{6}}&1&\frac{7}{4\sqrt{3}}\\\\[5.16663pt]
\frac{5}{4}&\frac{3}{2\sqrt{2}}&\frac{7}{4\sqrt{3}}&1\\\\[5.16663pt]
\end{pmatrix}\approx\begin{pmatrix}1.0000&1.0607&1.1547&1.2500\\\
1.0607&1.0000&1.0206&1.0607\\\ 1.1547&1.0206&1.0000&1.0104\\\
1.2500&1.0607&1.0104&1.0000\\\ \end{pmatrix}.$

For a chemical graph $G$, let $n_{i}(G)$ ($i=0,\ldots,4$) be the number of
vertices of degree $i$ and let $x_{i,j}(G)$ ($1\leq i\leq j\leq 4$) be the
number of edges with extremities of degrees $i$ and $j$ in $G$. Then, since
$C_{\texttt{AG}}$ is symmetric, we have

$\texttt{AG}(G)=\sum_{1\leq i\leq j\leq 4}c_{i,j}\,x_{i,j}(G).$

In what follows, we say that a chemical graph $G$ is _extremal_ if
$\texttt{AG}(G)\geq\texttt{AG}(G^{\prime})$ for all chemical graphs
$G^{\prime}$ with the same order and the same size as $G$.

##  3 Preliminaries

We begin this section with the definition of a class of chemical graphs which,
as we will see, contains most of the extremal chemical graphs of order $n$ and
size $m$.

######  Definition 1.

$\mathcal{G}_{n,m}$ is the set of chemical graphs of order $n$ and size $m$,
and such that $n_{0}(G)=0$, $n_{2}(G)+n_{3}(G)\leq 1$ and all edges have at
least one endpoint of degree 4.

For example, using _Nauty geng_ [10] or _PHOEG_ [6] to enumerate all chemical
graphs having order $n$ and size $m$, it can be observed that there is only
one graph $G_{n,m}$ in $\mathcal{G}_{n,m}$ for $(n,m)=(5,4)$, $(6,10)$,
$(7,7)$, $(7,9)$, $(8,9)$, $(9,8)$, $(9,9)$ and $(11,11)$, and there are two
graphs in $G_{12,11}$, one connected and one non-connected (see also Table 3
at the end of the paper). These graphs are shown in Figure 1 and they were
chosen because they will appear in the proofs of the next sections.

Figure 1: Examples of graphs in $\mathcal{G}_{n,m}$ for some pairs $(n,m)$.

If all edges of a chemical graph $G$ have at least one endpoint of degree 4,
then
$\texttt{AG}(G)=c_{1,4}n_{1}(G)+2c_{2,4}n_{2}(G)+3c_{3,4}n_{3}(G)+(m-n_{1}(G)-2n_{2}(G)-3n_{3}(G))$
and since $2m=n_{1}(G)+2n_{2}(G)+3n_{3}(G)+4n_{4}(G)$, we have

$\displaystyle\texttt{AG}(G)$ $\displaystyle=$ $\displaystyle
c_{1,4}n_{1}(G)+2c_{2,4}n_{2}(G)+3c_{3,4}n_{3}(G)+4n_{4}(G)-m$
$\displaystyle=$ $\displaystyle
c_{1,4}n_{1}(G)+2c_{2,4}n_{2}(G)+3c_{3,4}n_{3}(G)+4n_{4}(G)$
$\displaystyle-\tfrac{1}{2}(n_{1}(G)+2n_{2}(G)+3n_{3}(G)+4n_{4}(G))$
$\displaystyle=$
$\displaystyle\tfrac{3}{4}n_{1}(G)+(\tfrac{3}{\sqrt{2}}-1)n_{2}(G)+(\tfrac{21}{4\sqrt{3}}-\tfrac{3}{2})n_{3}(G)+2n_{4}(G).$

For a pair $(n,m)$ of integers, let $T_{n,m}$ be the set of quadruplets
$(t_{1},t_{2},t_{3},t_{4})$ of positive integers such that
$\sum_{i=1}^{4}t_{i}=n$ and $\sum_{i=1}^{4}it_{i}=2m$. Hence, we have
$2m-n=t_{2}+2t_{3}+3t_{4}$. Note that $T_{1,0}=\emptyset$ since
$\sum_{i=1}^{4}t_{i}\leq\sum_{i=1}^{4}it_{i}$. For
$(t_{1},t_{2},t_{3},t_{4})\in T_{n,m}$, let $f(t_{1},t_{2},t_{3},t_{4})$ be
defined as

$f(t_{1},t_{2},t_{3},t_{4})=\tfrac{3}{4}t_{1}+(\tfrac{3}{\sqrt{2}}-1)t_{2}+(\tfrac{21}{4\sqrt{3}}-\tfrac{3}{2})t_{3}+2t_{4}.$

Clearly, if $G$ is a chemical graph of order $n$ and size $m$, with no
isolated vertex and in which all edges have at least one endpoint of degree 4,
then $(n_{1}(G),n_{2}(G),n_{3}(G),n_{4}(G))$ belongs to $T_{n,m}$ and we have
observed above that

$\texttt{AG}(G)=f(n_{1}(G),n_{2}(G),n_{3}(G),n_{4}(G)).$

Let $(t_{1},t_{2},t_{3},t_{4})$ be a quadruplet in $T_{n,m}$ with
$t_{2}+t_{3}\leq 1$:

  * •

if $t_{2}=1$ then $t_{3}=0$, which means that $2m-n=3t_{4}+1$ and
$2m=t_{1}+2+4(n-t_{1}-1)$, or equivalently, $t_{1}=\frac{4n-2m-2}{3}$;

  * •

if $t_{3}=1$ then $t_{2}=0$, which means that $2m-n=3t_{4}+2$ and
$2m=t_{1}+3+4(n-t_{1}-1)$, or equivalently, $t_{1}=\frac{4n-2m-1}{3}$;

  * •

if $t_{2}=t_{3}=0$, then $2m-n=3t_{4}$ and $2m=t_{1}+4(n-t_{1})$, or
equivalently, $t_{1}=\frac{4n-2m}{3}$.

Hence in all cases, we deduce the following property.

######  Property 1.

If $(t_{1},t_{2},t_{3},t_{4})$ is a quadruplet in $T_{n,m}$ with
$t_{2}+t_{3}\leq 1$, then

  * •

$t_{1}=\lfloor\frac{4n-2m}{3}\rfloor$

  * •

$t_{2}=\left\\{\begin{array}[]{ll}1&\mbox{\emph{if} }2m-n\equiv 1\bmod{3}\\\
0&\mbox{\emph{otherwise}}\end{array}\right.$

  * •

$t_{3}=\left\\{\begin{array}[]{ll}1&\mbox{\emph{if} }2m-n\equiv 2\bmod{3}\\\
0&\mbox{\emph{otherwise}}\end{array}\right.$

  * •

$t_{4}=\lfloor\frac{2m-n}{3}\rfloor$.

######  Corollary 1.

There is at most one quadruplet $(t_{1},t_{2},t_{3},t_{4})$ in $T_{n,m}$ with
$t_{2}+t_{3}\leq 1$.

######  Corollary 2.

If $G$ is a graph in $\mathcal{G}_{n,m}$, then the quadruplet
$(t_{1},t_{2},t_{3},t_{4})=(n_{1}(G),n_{2}(G),n_{3}(G),n_{4}(G))$ is the
unique one in $T_{n,m}$ with $t_{2}+t_{3}\leq 1$.

###### Proof.

Let $G$ be a graph in $\mathcal{G}_{n,m}$. Then $\sum_{i=1}^{4}n_{i}(G)=n$ and
$\sum_{i=1}^{4}in_{i}(G)=2m$, which means that
$(t_{1},t_{2},t_{3},t_{4})=(n_{1}(G),n_{2}(G),n_{3}(G),n_{4}(G))$ is a
quadruplet in $T_{n,m}$ with $t_{2}+t_{3}\leq 1$. By Corollary 1, it is
unique. ∎

Some connected extremal chemical graphs have all edges with at least one
endpoint of degree 4, but have $n_{0}(G)>0$ or $n_{2}(G)+n_{3}(G)>1$. Seven
examples are shown in Figure 2 and we will prove that there are no other ones.

Figure 2: Seven connected extremal chemical graphs with all edges having at
least one endpoint of degree 4 and with $n_{0}(G)>0$ or $n_{2}(G)+n_{3}(G)>1$.

Also, some connected extremal chemical graphs have at least one edge with no
endpoint of degree 4. Fifteen examples are shown in Figure 3 and we will prove
that there are no other ones.

Figure 3: Fifteen connected extremal chemical graphs with at least one edge
having no endpoint of degree 4.

For each pair $(n,m)$ such that $H_{n,m}$ appears in Figure 2 or 3, we can
enumerate all chemical graphs having order $n$ and size $m$, using again
_Nauty geng_ [10] or _PHOEG_ [6]. Table 1 gives the number of such graphs and
it is therefore easy to verify that the following property holds.

######  Property 2.

The 22 graphs in Figures 2 and 3 are the only extremal graphs of their order
and size.

Table 1: Number $N$ of chemical graphs for some orders $n$ and sizes $m$. $n$ | 1 | 2 | 3 | 3 | 4 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 6 | 6 | 6 | 6 | 6 | 7 | 7 | 8 | 10
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$m$ | 0 | 1 | 2 | 3 | 3 | 4 | 5 | 6 | 5 | 6 | 7 | 8 | 9 | 5 | 6 | 7 | 8 | 9 | 6 | 8 | 8 | 9
$N$ | 1 | 1 | 1 | 1 | 3 | 2 | 1 | 1 | 6 | 6 | 4 | 2 | 1 | 14 | 20 | 22 | 20 | 15 | 38 | 82 | 188 | 883

The next property relates quadruplets in $T_{n,m}$ with connected graphs in
$\mathcal{G}_{n,m}$. Note that a connected chemical graph of order $n$ has $m$
edges, with $n-1\leq m\leq\min\\{2n,\tfrac{n(n-1)}{2}\\}$.

######  Property 3.

Let $n$ and $m$ be two positive integers such that $n-1\leq
m\leq\min\\{2n,\tfrac{n(n-1)}{2}\\}$ and $(n,m)$ is not one of the 22 pairs
for which there is a graph $H_{n,m}$ in Figure 2 or 3. If
$(t_{1},t_{2},t_{3},t_{4})\in T_{n,m}$ and $t_{2}+t_{3}\leq 1$, then
$\mathcal{G}_{n,m}$ contains at least one connected graph $G$ with
$n_{i}(G)=t_{i}$ ($i=1,2,3,4$).

###### Proof.

Consider a pair $(n,m)$ of positive integers such that $n-1\leq
m\leq\min\\{2n,\tfrac{n(n-1)}{2}\\}$ and let $(t_{1},t_{2},t_{3},t_{4})$ be
any quadruplet in $T_{n,m}$. Note that $n\geq 2$ since $T_{1,0}=\emptyset$.
According to Property 1 and Corollary 2, a graph in $\mathcal{G}_{n,m}$ with
$n_{i}(G)=t_{i}$ ($i=1,2,3,4$) must have

  * •

$n_{1}(G)=\lfloor\frac{4n-2m}{3}\rfloor$

  * •

$n_{2}(G)=\left\\{\begin{array}[]{ll}1&\mbox{if }2m-n\equiv 1\bmod{3}\\\
0&\mbox{otherwise}\end{array}\right.$

  * •

$n_{3}(G)=\left\\{\begin{array}[]{ll}1&\mbox{if }2m-n\equiv 2\bmod{3}\\\
0&\mbox{otherwise}\end{array}\right.$

  * •

$n_{4}(G)=\lfloor\frac{2m-n}{3}\rfloor$.

Moreover, in order to impose that all edges in $G$ have at least one endpoint
of degree 4, we must have

  * •

$x_{1,1}(G)=x_{1,2}(G)=x_{1,3}(G)=x_{2,2}(G)=x_{2,3}(G)=x_{3,3}(G)=0$,

  * •

$x_{1,4}(G){=}n_{1}(G)$, $x_{2,4}(G){=}2n_{2}(G)$, $x_{3,4}(G){=}3n_{3}(G)$,
$x_{4,4}(G){=}m{-}n_{1}(G){-}2n_{2}(G){-}3n_{3}(G)$.

The following algorithm builds such a connected graph $G$, where $V_{i}$
($i=1,\ldots,4$) is the set of vertices of degree $i$ in $G$. It is
illustrated in Figure 4.

  * 1.

Start from a graph of order $n$ and size $0$. Put $n_{i}(G)$ vertices in
$V_{i}$, $i=1,\ldots,4$;

  * 2.

if $2m-n\equiv 1\bmod{3}$ then connect the vertex in $V_{2}$ to 2 vertices in
$V_{4}$;

  * 3.

if $2m-n\equiv 2\bmod{3}$ then connect the vertex in $V_{3}$ to 3 vertices in
$V_{4}$;

  * 4.

add $n_{4}(G){-}n_{2}(G){-}2n_{3}(G){-}1$ edges that link pairs of vertices in
$V_{4}$ so that the graph induced by $V_{2}\cup V_{3}\cup V_{4}$ is a tree;

  * 5.

add $m-n_{1}(G)-n_{2}(G)-n_{3}(G)-n_{4}(G)+1$ edges that link pairs of
vertices in $V_{4}$ so that no vertex in $V_{4}$ is incident to more than 4
edges;

  * 6.

add edges linking each vertex of $V_{1}$ to a vertex of $V_{4}$ so that every
vertex in $V_{4}$ has degree 4.

Steps 2 and 3 add the required number of edges with one endpoint of degree 4
and the other of degree 2 or 3, and Step 6 adds the required number of edges
with one endpoint of degree 4 and the other of degree 1. Step 4 adds
$n_{4}(G){-}n_{2}(G){-}2n_{3}(G){-}1$ edges linking pairs of vertices in
$V_{4}$, while Step 5 adds $m-n_{1}(G)-n_{2}(G)-n_{3}(G)-n_{4}(G)+1$ such
edges. In total we will therefore have $m-n_{1}(G)-2n_{2}(G)-3n_{3}(G)$ edges
linking pairs of vertices of $V_{4}$, which is the required number of edges
with both endpoints of degree 4. It remains to prove that such a construction
is always possible. For this purpose, the following constraints must be
satisfied :

  * •

$2n_{2}(G)\leq n_{4}(G)$ and $3n_{3}(G)\leq n_{4}(G)$ to ensure that Steps 2
and 3 can be performed;

  * •

$m{-}n_{1}(G){-}2n_{2}(G){-}3n_{3}(G)\leq\tfrac{n_{4}(G)(n_{4}(G){-}1)}{2}$ to
avoid creating parallel edges in Steps 4 and 5;

  * •

$n_{1}(G)\leq 4n_{4}(G)$, to ensure that Step 6 can be performed.

It is easy to check that these conditions are satisfied for all pairs $(n,m)$
with $n\leq 13$ and $n-1\leq m\leq\min\\{2n,\tfrac{n(n-1)}{2}\\}$, except for
the 22 pairs for which we have a graph $H_{n,m}$ in Figures 2 or 3. So assume
$n\geq 14$. We then have

  * •

$n_{4}(G)\geq\frac{2m-n-2}{3}\geq\frac{n-4}{3}>3\geq\max\\{2n_{2}(G),3n_{3}(G)\\}$
(since $n_{1}(G)+n_{2}(G)\leq 1$).

$\displaystyle\bullet\;\;\frac{n_{4}(G)(n_{4}(G){-}1)}{2}{-}x_{4,4}(G)$
$\displaystyle\geq\frac{1}{2}\Biggl{(}\frac{2m{-}n{-}2}{3}\left(\frac{2m{-}n{-}2}{3}{-}1\right)\Biggr{)}$
$\displaystyle{-}\left(m{-}\frac{4n{-}2m{-}2}{3}\right)$
$\displaystyle=\frac{4m(m-n-11)+n^{2}+31n-2}{18}$
$\displaystyle\geq\frac{4(n{-}1)(n{-}1{-}n{-}11){+}n^{2}{+}31n{-}2}{18}$
$\displaystyle=\frac{n^{2}-17n+46}{18}>0.$

  * •

$4n_{4}(G)-n_{1}(G)\geq\frac{4(2m-n)}{3}-\frac{4n-2m+2}{3}=\frac{10m-8n-2}{3}\geq\frac{10(n-1)-8n-2}{3}=\frac{2n}{3}-4>0$.

In summary, $G$ has the right number of edges of each type and thanks to Step
4, it is connected. ∎

The algorithm in the above proof is illustrated in Figure 4 for $n=m=17$. In
such a case, we have $n_{1}(G)=11$, $n_{2}(G)=0$, $n_{3}(G)=1$, $n_{4}(G)=5$
and $x_{4,4}(G)=3$. In Step 1, we have represented the vertices of $V_{1}$
with the white color, while the vertex in $V_{3}$ is grey and the vertices in
$V_{4}$ are black. Step 3 links the grey vertex to 3 black vertices. Step 4
adds 2 edges between black vertices. Step 5 adds the last edge between two
black vertices and Step 6 adds the edges between the white and the black
vertices. Notice that Step 4 was crucial to obtain a connected graph. Indeed
another set of 3 edges linking black vertices could have produced a non-
connected graph in $\mathcal{G}_{n,m}$ as illustrated at the bottom right of
Figure 4.

Figure 4: Illustration of the algorithm in the proof of Theorem 1

The main objective of this paper is to prove the following theorem.

######  Theorem 1.

Let $G$ be a connected chemical graph of order $n$ and size $m$. If $G$ is
extremal, then either $G$ is one of the 22 graphs $H_{n,m}$ of Figures 2 and
3, or $G$ belongs to $\mathcal{G}_{n,m}$.

To prove this theorem, we need some tools which are given in the next section.

##  4 Tools

######  Lemma 1.

Let $G$ be a connected extremal chemical graph. Assume that $G$ has a vertex
$u$ of degree 2 where $v$ and $w$ are its two neighbors.

  * (a)

If $v$ and $w$ are nonadjacent, then none of them has degree 3.

  * (b)

If $v$ and $w$ are adjacent, $d_{v}{\geq}3$ and $d_{w}{\leq}3$, then no vertex
nonadjacent to $w$ has degree 2 or 3.

###### Proof.

  * (a)

Assume that $v$ and $w$ are nonadjacent, and that one of them, say $v$, has
degree 3. Let $G^{\prime}$ be the graph obtained from $G$ by replacing $uw$
with $vw$. Then, with $i=d_{u}$ and $j=d_{x}$, where $x$ is any neighbor of
$v$ other than $u$, we have

$\displaystyle\texttt{AG}(G^{\prime}){-}\texttt{AG}(G)$ $\displaystyle\geq
c_{1,4}-c_{2,3}+\min_{i=1,\ldots 4}(c_{4,i}-c_{2,i})+2\min_{j=1,\ldots
4}(c_{4,j}{-}c_{3,j})$ $\displaystyle\approx 0.1479>0.$

  * (b)

Assume that $v$ and $w$ are adjacent with $d_{v}\geq 3$ and $d_{w}\leq 3$, and
let $x$ be a vertex nonadjacent to $w$ such that $d_{x}=2$ or 3. Let
$G^{\prime}$ be the graph obtained from $G$ by replacing $uw$ with $xw$. Then,
with $i=d_{v}$, $j=d_{w}$, $k=d_{x}$ and $\ell=d_{y}$, where $y$ is any
neighbor of $x$, we have

$\displaystyle\texttt{AG}(G^{\prime}){-}\texttt{AG}(G)\;{\geq}$
$\displaystyle\;\min_{i=3,4}(c_{1,i}-c_{2,i})$
$\displaystyle\;{+}\min_{k=2,3}{\bigg{(}}\min_{j=2,3}(c_{j,k{+}1}{-}c_{j,2}){+}k\min_{\ell=1,\ldots,4}(c_{\ell,k{+}1}{-}c_{\ell,k}){\bigg{)}}$
$\displaystyle\;{\approx}$ $\displaystyle\;0.0128>0.$

In both cases, $G^{\prime}$ is connected and
$\texttt{AG}(G^{\prime})>\texttt{AG}(G)$, which means that $G$ is not an
extremal, connected chemical graph, a contradiction. ∎

######  Lemma 2.

A connected extremal chemical graph does not contain a chain
$v_{1},v_{2},\ldots,v_{r}$ as partial subgraph with $v_{1}$ nonadjacent to
$v_{r-1}$ and $v_{2}$ nonadjacent to $v_{r}$ in $G$ and with
$d_{v_{1}}<d_{v_{r}}$, $d_{v_{2}}\leq 3$, and $d_{v_{r-1}}=4$.

###### Proof.

Let $G^{\prime}$ be the graph obtained from $G$ by replacing the edges
$v_{1},v_{2}$ and $v_{r-1},v_{r}$ by $v_{1},v_{r-1}$ and $v_{2},v_{r}$. Then,
with $d_{v_{1}}=i$, $d_{v_{2}}=j$ and $d_{v_{r}}=k$, we have

$\texttt{AG}(G^{\prime})-\texttt{AG}(G)\geq\min_{i=1,2,3}\;\;\min_{j=2,3}\;\;\min_{k=i+1,\ldots,4}(c_{i,4}+c_{j,k}-c_{i,j}-c_{4,k})\approx
0.0207>0.$

Since $G^{\prime}$ is connected and $\texttt{AG}(G^{\prime})>\texttt{AG}(G)$,
this means that $G$ is not an extremal, connected chemical graph, a
contradiction. ∎

The next lemmas have a label $(i,j)$ with $i<j$ to indicate that they state
that a connected extremal chemical graph $G$ has $x_{i,j}(G)=0$, with a few
exceptions.

######  Lemma (1,1).

The only connected extremal chemical graph $G$ with $x_{1,1}(G)>0$ is
$H_{2,1}$.

###### Proof.

Let $G$ be a connected extremal chemical graph with two adjacent vertices of
degree 1. Since $G$ is connected, it does not contain any other vertex, which
means that $G\simeq H_{2,1}$. ∎

######  Lemma (2,2).

The only connected extremal chemical graphs $G$ with$x_{2,2}(G){>}0$ are
$H_{3,3}$, $H_{4,4}$ and $H_{5,5}$.

###### Proof.

Let $u$ and $v$ be two adjacent vertices of degree 2 in a connected extremal
chemical graph $G$.

  * •

Assume that $u$ and $v$ have a common neighbor $w$. If $w$ has degree 2, then
$G\simeq H_{3,3}$. So suppose $w$ has degree at least 3. We know from Lemma
1(b) that all other vertices in the graph have degree 1 or 4. If they have all
degree 1, then $G\simeq H_{4,4}$ (if $w$ has degree 3) or $G\simeq H_{5,5}$
(if $w$ has degree 4). So assume $w$ is adjacent to a vertex $x$ of degree 4.
If $x$ is adjacent to a vertex $y\neq w$ of degree 4, then Lemma 2 with the
partial chain $u,v,w,x,y$ contradicts the fact that $G$ is a connected
extremal chemical graph. Hence, all neighbors $y\neq w$ of $x$ have degree 1.
Similarly, if $w$ has a second neighbor $z$ of degree 4, then all neighbors of
$z$, except $w$, have degree 1. There are therefore only three possible cases:

    * –

if $w$ has degree 3 then $\texttt{AG}(G)\approx
7.80<8.12\approx\texttt{AG}(G_{7,7})$ (see Figure 1);

    * –

if $w$ has degree 4 and a neighbor of degree 1, then $\texttt{AG}(G)\approx
9.12<9.24\approx\texttt{AG}(H_{8,8})$ (see Figure 2);

    * –

if $w$ has degree 4 and a second neighbor of degree 4, then
$\texttt{AG}(G)\approx 12.62<12.78\approx\texttt{AG}(G_{11,11})$ (see Figure
1);

In all cases $G$ is not a connected extremal chemical graph, a contradiction.

  * •

Assume that $u$ and $v$ have no common neighbor. Let $x\neq v$ (resp. $y\neq
u$) be the second neighbor of $u$ (resp. $v$). Let $G^{\prime}$ be the graph
obtained from $G$ by replacing $xu$ with $xv$. Then, with $i=d_{x}$ and
$j=d_{y}$, we have

$\displaystyle\texttt{AG}(G^{\prime})-\texttt{AG}(G)$ $\displaystyle\geq
c_{1,3}-c_{2,2}+\min_{i=1,\ldots 4}(c_{3,i}-c_{2,i})+\min_{j=1,\ldots
4}(c_{3,j}-c_{2,j})$ $\displaystyle\approx 0.0541>0.$

Hence, $G$ is not extremal, a contradiction.∎

######  Lemma (1,2).

The only connected extremal chemical graphs $G$ with $x_{1,2}(G)>0$ are
$H_{3,2}$ and $H_{6,5}$.

###### Proof.

Let $G$ be a connected extremal chemical graph with two adjacent vertices $u$
and $v$ such that $d_{u}=1$ and $d_{v}=2$, and let $w$ be the other neighbor
of $v$. If $w$ has degree 1 then $G\simeq H_{3,2}$. We know from Lemma (2,2)
that $w$ does not have degree 2, and from Lemma 1(a) that $w$ does not have
degree 3. Hence, $d_{w}=4$. If $w$ has three neighbors of degree 1, then
$G\simeq H_{6,5}$; otherwise, $w$ has a neighbor $x\neq v$ of degree at least
2 and Lemma 2 with the partial chain $u,v,w,x$ contradicts the fact that $G$
is a connected extremal chemical graph. ∎

######  Lemma (3,3).

The only connected extremal chemical graphs $G$ with$x_{3,3}(G)>0$ are
$H_{4,5}$, $H_{4,6}$, $H_{5,8}$ and $H_{6,8}$.

###### Proof.

Let $G$ be a connected extremal = chemical graph with two adjacent vertices
$u$ and $v$ of degree 3. Let us first show that all vertices $x\neq u,v$ are
either adjacent to both $u$ and $v$, or to neither. If this is not the case
then, we consider two cases.

  * •

If $u$ and $v$ have a common neighbor $w$, then let $x\neq v$ be a vertex
adjacent to $u$ but not to $v$, and let $y\neq u$ be a vertex adjacent to $v$
but not to $u$. Then $G$ is not extremal. Indeed, let $G^{\prime}$ be the
graph obtained from $G$ by replacing $xu$ with $xv$. Then, with $i=d_{x}$,
$j=d_{y}$ and $k=d_{w}$, we have

$\displaystyle\texttt{AG}(G^{\prime})-\texttt{AG}(G)$ $\displaystyle{\geq}$
$\displaystyle c_{2,4}-c_{3,3}+\min_{i=1,2,3,4}(c_{4,i}{-}c_{3,i})$
$\displaystyle+\min_{j=1,2,3,4}(c_{4,j}{-}c_{3,j})+\min_{k=2,3,4}(c_{4,k}{+}c_{2,k}{-}2c_{3,k})$
$\displaystyle{\approx}$ $\displaystyle 0.0593>0.$

  * •

If $u$ and $v$ have no common neighbor, then there are two possible cases.

    * –

if all neighbors $x\neq u,v$ of $u$ and $v$ have degree 1, then $G$ is not
extremal since $\texttt{AG}(G)\approx 5.62<5.87\approx\texttt{AG}(H_{6,5})$
(see Figure 3);

    * –

if at least one of $u,v$, say $u$, has a neighbor $x\neq v$ of degree at least
2, then $G$ is not extremal. Indeed, let $y$ be the other neighbor of $u$ and
let $G^{\prime}$ be the graph obtained from $G$ by replacing $yu$ with $yv$.
Then, with $i=d_{x}$, $j=d_{y}$ and $k=d_{z}$, where $z$ is any neighbor of
$v$ other than $u$, we have

$\displaystyle\texttt{AG}(G^{\prime}){-}\texttt{AG}(G)$ $\displaystyle\geq$
$\displaystyle c_{2,4}{-}c_{3,3}+\min_{i=2,3,4}(c_{2,i}{-}c_{3,i})$
$\displaystyle+\min_{j=1,2,3,4}(c_{4,j}{-}c_{3,j})+2\min_{k=1,2,3,4}(c_{4,k}{-}c_{3,k})$
$\displaystyle\approx$ $\displaystyle 0.0089>0.$

Hence, let $x,y$ the the two common neighbors of $u$ and $v$. We next show
that at least one of $x,y$ has degree 4, or $G$ is $H_{4,5}$ or $H_{4,6}$.

  * •

If $x$ has degree 3, then $x$ is adjacent to $y$ since $xu$ is an edge linking
two vertices of degree 3 and we have seen that this implies that $y$ cannot be
adjacent to exactly one of $u,x$. Hence, either $G\simeq H_{4,6}$, or $y$ has
degree 4.

  * •

If $x$ has degree 2, then we know from the previous case that $y$ is of degree
2 or 4. Hence, either $G\simeq H_{4,5}$, or $y$ has degree 4.

So, without loss of generality, assume $d_{x}=4$. Let
$W=V\setminus\\{u,v,x,y\\}$ where $V$ is the vertex set of $G$. Assume that
$W$ contains at least one vertex $w$ in $W$ of degree at least 3.

  * •

If $d_{w}=4$, then let $z$ be a vertex adjacent to $w$ but not to $x$ and let
$G^{\prime}$ be the graph obtained from $G$ by replacing the edges $ux$ and
$wz$ by $uw$ and $xz$. Clearly, $\texttt{AG}(G^{\prime})=\texttt{AG}(G)$,
which means that $G^{\prime}$ is also a connected extremal chemical graph. But
$u$ and $v$ are two adjacent vertices in $G^{\prime}$, and they are both of
degree 3, while $x$ is adjacent to $u$ but not to $v$. We have shown above
that this is impossible.

  * •

If $d_{w}=3$, then $w$ is adjacent to $x$. Indeed, if this is not the case,
then let $z$ be any vertex in $W$ adjacent to $w$ and let $G^{\prime}$ be the
graph obtained from $G$ by replacing the edges $ux$ and $wz$ by $uz$ and $xw$.
Clearly, $\texttt{AG}(G^{\prime})=\texttt{AG}(G)$ and $u,v$ are two adjacent
vertices of degree 3 in $G^{\prime}$ with $z$ adjacent to $u$ but not to $v$,
a contradiction. Moreover, all neighbors of $w$ in $W$ are adjacent to $x$.
Indeed, assume that a vertex $z\in W$ is adjacent to $w$ but not to $x$. Then
$d_{z}\leq 2$ (since vertices of degree 3 in $W$ are adjacent to $x$ and no
vertex in $W$ has degree 4), and Lemma 2 with the partial chain $z,w,x,u$
shows that $G$ is not extremal, a contradiction. In summary, we have shown
that $w$ can have only one neighbor in $W$ (else $x$ would be of degree at
least 5), which means that $w$ is adjacent to $y$. We know from Lemma 1(b)
that the neighbor $z$ of $w$ in $W$ cannot be of degree 2 (since $u$ has
degree 3 and is not adjacent to $w$). Hence, $d_{z}=3$, which means that $w,x$
and $y$ are its three neighbors (as $z,x,y$ are the 3 neighbors of $w$).
Hence, $\texttt{AG}(G)\approx 10.08<10.28\approx\texttt{AG}(G_{6,10})$ (see
Figure 1), a contradiction.

Hence, all vertices in $W$ have degree 1 or 2. At least one vertex in $W$ has
degree 2, else

  * •

if $d_{y}=3$, then $x$ is adjacent to $y$ since $uy$ is an edge linking two
vertices of degree 3 and we have seen that this implies that $x$ cannot be
adjacent to exactly one of $u,y$. Hence, $\texttt{AG}(G)\approx
7.28<7.36\approx\texttt{AG}(H_{5,7})$ (see Figure 2);

  * •

if $d_{y}=4$, then either $G\simeq H_{6,8}$, or $\texttt{AG}(G)\approx
10.04<10.12\approx\texttt{AG}(G_{8,9})$ (see Figure 1).

So let $z$ be a vertex of degree 2 in $W$. We know from Lemmas (2,2) and (1,2)
that $z$ is adjacent to $x$ and $y$, which implies that $y$ has degree 4, else
$u$ and $y$ are two adjacent vertices of degree 3 and $z$ is adjacent to $y$
but not to $u$, which is impossible. There are therefore three possible cases:

  * •

if $W$ has two vertices of degree 2, then $\texttt{AG}(G)\approx
9.28<9.40\approx\texttt{AG}(H_{6,9})$ (see Figure 2);

  * •

if $W$ has one vertex of degree 2 and $x$ is not adjacent to $y$, then
$\texttt{AG}(G)\approx 9.66<9.78\approx\texttt{AG}(G_{7,9})$ (see Figure 1);

  * •

if $W$ has one vertex of degree 2 and $x$ is adjacent to $y$, then $G\simeq
H_{5,8}$.∎

######  Lemma (1,3).

The only connected extremal chemical graphs $G$ with$x_{1,3}(G)>0$ are
$H_{4,3}$, $H_{4,4}$, $H_{6,6}$, $H_{7,6}$ and $H_{10,9}$.

###### Proof.

Let $G$ be a connected extremal chemical graph with two adjacent vertices $u$
and $v$ such that $d_{u}=1$ and $d_{v}=3$. If $v$ has a neighbor $w$ of degree
2, we know from Lemma 1(a) that the second neighbor $x$ of $w$ is adjacent to
$v$. Then, either $G\simeq H_{4,4}$ or it follows from Lemmas (2,2) and (3,3)
that $d_{x}=4$. If $x$ has two neighbors of degree 1, then $G\simeq H_{6,6}$,
else $x$ has a neighbor $y\neq v,w$ such that $d_{y}\geq 2$, and Lemma 2 with
the partial chain $u,v,x,y$ shows that $G$ is not extremal, a contradiction.

So assuming that $G$ is not $H_{4,4}$ or $H_{6,6}$, we know that no neighbor
of $v$ has degree 2. It then follows from Lemma (3,3) that they all have
degree 1 or 4. If $v$ has a neighbor $x$ of degree 4, then all neighbors
$y\neq v$ of $x$ that are also not adjacent to $v$ have degree 1, else Lemma 2
with the partial chain $u,v,x,y$ shows that $G$ is not extremal. Hence there
are only 4 cases:

  * •

if all neighbors of $v$ have degree 1, then $G\simeq H_{4,3}$;

  * •

if $v$ has only one neighbor of degree 4, then $G\simeq H_{7,6}$;

  * •

if $v$ has two non-adjacent neighbors of degree 4, then $G\simeq H_{10,9}$;

  * •

if $v$ has two adjacent neighbors of degree 4, then $\texttt{AG}(G)\approx
9.18<9.24\approx\texttt{AG}(H_{8,8})$ (see Figure 2).∎

######  Lemma (2,3).

The only connected extremal chemical graphs $G$ with$x_{2,3}(G)>0$ are
$H_{4,4}$, $H_{4,5}$, $H_{5,6}$ and $H_{6,6}$.

###### Proof.

Let $G$ be a connected extremal chemical graph with two adjacent vertices $u$
and $v$ such that $d_{u}=2$ and $d_{v}=3$. We know from Lemma 1(a) that the
second neighbor $w$ of $u$ is adjacent to $v$. If $G$ is not equal to
$H_{4,4}$ or $H_{4,5}$, it follows from Lemmas (2,2) and (3,3) that $w$ has
degree 4. Also, it follows from Lemmas (1,3) and (3,3) that if $G$ is not
$H_{6,6}$, then the third neighbor $x\neq u,w$ of $v$ has degree 2 or 4.

  * •

If $d_{x}=2$, then $x$ is adjacent to $w$ since, by Lemma 1(a), the second
neighbor of $x$ must be adjacent to $v$. It follows from Lemma 1(b) that all
vertices other than $u,v,w,x$ have degree 1 or 4. Hence, the fourth neighbor
$y\neq u,v,x$ of $w$ has degree 1 or 4. If $d_{y}=1$ then $G\simeq H_{5,6}$.
If $d_{y}=4$, then there are two cases:

    * –

if $y$ has 3 neighbors of degree 1, then $\texttt{AG}(G)\approx
9.92<10.12\approx\texttt{AG}(G_{8,9})$ (see Figure 1);

    * –

if $y$ has a neighbor $z\neq w$ of degree 4, then Lemma 2 with the partial
chain $u,v,w,y,z$ shows that $G$ is not extremal, a contradiction.

  * •

If $d_{x}=4$, then let $y\neq v,w$ be a neighbor of $x$. It follows from
Lemmas 1(b) and 2 with the partial chain $u,v,x,y$ that $d_{y}=1$. Let
$G^{\prime}$ be the graph obtained from $G$ by replacing the edges $uw$ and
$xy$ by $ux$ and $wy$. Clearly, $\texttt{AG}(G^{\prime})=\texttt{AG}(G)$,
which means that $G^{\prime}$ is also a connected extremal chemical graph and
since $w$ is now the neighbor of $v$ of degree 4 that is not adjacent to $u$,
this means that all neighbors of $w$ different from $v,x$ have degree 1.
Hence,

    * –

if $w$ is adjacent to $x$ then $\texttt{AG}(G)\approx
8.85<8.86\approx\texttt{AG}(H_{7,8})$ (see Figure 2);

    * –

if $w$ is not adjacent to $x$ then $\texttt{AG}(G)\approx
10.35<10.5\approx\texttt{AG}(G_{9,9})$ (see Figure 1).∎

##  5 Characterization of extremal chemical graphs

In this section, we characterize extremal chemical graphs of order $n$ and
size $m\geq n-1$. We first consider the connected extremal chemical graphs,
and then the non-connected ones. We conclude the section with a property of
extremal chemical graphs or order $n$ and size $m\leq n-2$.

We start with the proof of Theorem 1 that states that a connected extremal
chemical graph of order $n$ and size $m$ necessarily belongs to
$\mathcal{G}_{n,m}$, except for 22 pairs $(n,m)$.

Proof of Theorem 1. Observe first that if $(t_{1},t_{2},t_{3},t_{4})$ is a
quadruplet in $T_{n,m}$ with $t_{2}+t_{3}>1$. Then there is
$(s_{1},s_{2},s_{3},s_{4})\in T_{n,m}$ such that $s_{2}+s_{3}<t_{1}+t_{2}$ and
$f(s_{1},x_{2},s_{3},s_{4})>f(t_{1},t_{2},t_{3},t_{4})$. Indeed:

  * •

If $t_{2}\geq 2$ then set $s_{1}=t_{1}+1$, $s_{2}=t_{2}-2$, $s_{3}=t_{3}+1$
and $s_{4}=t_{4}$. We have, $\sum_{i=1}^{4}s_{i}=\sum_{i=1}^{4}t_{i}=n$ and
$\sum_{i=1}^{4}is_{i}=\sum_{i=1}^{4}it_{i}=2m$, which means that
$(s_{1},s_{2},s_{3},s_{4})\in T_{n,m}$. Moreover,

$f(s_{1},s_{2},s_{3},s_{4})-f(t_{1},t_{2},t_{3},t_{4})=c_{1,4}-4c_{2,4}+3c_{3,4}\approx
0.0384>0.$

  * •

if $t_{3}\geq 2$ then set $s_{1}=t_{1}$, $s_{2}=t_{2}+1$, $s_{3}=t_{3}-2$ and
$s_{4}=t_{4}+1$. We have $\sum_{i=1}^{4}s_{i}=\sum_{i=1}^{4}t_{i}=n$ and
$\sum_{i=1}^{4}is_{i}=\sum_{i=1}^{4}it_{i}=2m$, which means that
$(s_{1},s_{2},s_{3},s_{4})\in T_{n,m}$. Moreover,

$f(s_{1},s_{2},s_{3},s_{4})-f(t_{1},t_{2},t_{3},t_{4})=2c_{2,4}-6c_{3,4}+4\approx
0.0591>0.$

  * •

if $t_{2}\geq 1$ and $t_{3}\geq 1$, then set $s_{1}=t_{1}+1$, $s_{2}=t_{2}-1$,
$s_{3}=t_{3}-1$ and $s_{4}=t_{4}+1$. Hence,
$\sum_{i=1}^{4}s_{i}=\sum_{i=1}^{4}t_{i}=n$ and
$\sum_{i=1}^{4}is_{i}=\sum_{i=1}^{4}it_{i}=2m$, which means that
$(s_{1},s_{2},s_{3},s_{4})\in T_{n,m}$. Moreover,

$f(s_{1},s_{2},s_{3},s_{4})-f(t_{1},t_{2},t_{3},t_{4})=c_{1,4}-2c_{2,4}-3c_{3,4}+4\approx
0.0975>0.$

Note that if $s_{2}+s_{3}>1$, then we can repeat the same reasoning. We can
therefore conclude that if $(t_{1},t_{2},t_{3},t_{4})$ is a quadruplet in
$T_{n,m}$ with $t_{2}+t_{3}>1$, then there is $(s_{1},s_{2},s_{3},s_{4})\in
T_{n,m}$ such that $s_{2}+s_{3}\leq 1$ and
$f(s_{1},s_{2},s_{3},s_{4})>f(t_{1},t_{2},t_{3},t_{4})$.

So let $G$ be a connected extremal chemical graph of order $n$ and size $m$,
and suppose that $G$ is not one of the 22 graphs of Figures 2 and 3. It
follows from the lemmas of the previous section that all edges in $G$ have at
least one endpoint of degree 4. Since $n_{0}(G)=0$ (else $G\simeq H_{1,0}$),
we have $\texttt{AG}(G)=f(n_{1}(G),n_{2}(G),n_{3}(G),n_{4}(G))$. We have shown
above that if $n_{2}(G)+n_{3}(G)>1$, then there is a quadruplet
$(s_{1},s_{2},s_{3},s_{4})$ in $T_{n,m}$ such that $s_{2}+s_{3}\leq 1$ and
$f(s_{1},s_{2},s_{3},s_{4})>f(n_{1}(G),n_{2}(G),n_{3}(G),n_{4}(G))$. Hence, if
$n_{2}(G)+n_{3}(G)>1$, then it follows from Property 3 that there is a
connected chemical graph $G^{\prime}$ in $\mathcal{G}_{n,m}$ with
$\texttt{AG}(G^{\prime})=f(s_{1},s_{2},s_{3},s_{4})>f(n_{1}(G),n_{2}(G),n_{3}(G),n_{4}(G))=\texttt{AG}(G)$,
a contradiction. We can therefore conclude that $n_{2}(G)+n_{3}(G)\leq 1$,
which implies that $G$ belongs to $\mathcal{G}_{n,m}$. ∎

It follows from Theorem 1 and Corollary 2 that if $1\leq n-1\leq m$ and
$(n,m)$ is not a pair for which there is a graph $H_{n,m}$ in Figure 2 or 3
and if there exists a connected extremal graph of order $n$ and size $m$, then
all graphs in $\mathcal{G}_{n,m}$ are extremal and their arithmetic-geometric
index is easy to compute since we know the number of edges with endpoints of
degree $i$ and $j$ for all $1\leq i\leq j\leq 4$. We can therefore state the
following corollary.

######  Corollary 3.

Let $G$ be a connected extremal chemical graph. If $G$ is not one of the 22
graphs $H_{n,m}$ in Figure 2, then $\emph{$\texttt{AG}$}(G)=U\\!B_{n,m}$,
where

$U\\!B_{n,m}=\frac{2n+5m}{6}+\left\\{\begin{array}[]{ll}0&\mbox{\emph{if}
}2m-n\equiv 0\bmod{3},\\\ \frac{3}{\sqrt{2}}-\frac{13}{6}&\mbox{\emph{if}
}2m-n\equiv 1\bmod{3},\\\ \frac{21}{4\sqrt{3}}-\frac{37}{12}&\mbox{\emph{if}
}2m-n\equiv 2\bmod{3}.\end{array}\right.$

###### Proof.

Theorem 1 shows that $G$ belongs to $\mathcal{G}_{n,m}$. Let us compute
$\texttt{AG}(G)$.

  * •

If $2m-n\equiv 0\bmod{3}$, then $4n-2m\equiv 0\bmod{3}$, which means that
$n_{1}(G){=}\frac{4n{-}2m}{3}$, $n_{2}(G){=}n_{3}(G){=}0$ and
$n_{4}(G){=}\frac{2m{-}n}{3}$. Hence,
$\texttt{AG}(G)=\tfrac{3}{4}\tfrac{4n-2m}{3}+2\tfrac{2m-n}{3}=\tfrac{2n+5m}{6}$.

  * •

If $2m{-}n\equiv 1\bmod{3}$, then $4n{-}2m\equiv 2\bmod{3}$, which means that
$n_{1}(G){=}\frac{4n{-}2m{-}2}{3}$, $n_{2}(G){=}1,n_{3}(G){=}0$ and
$n_{4}(G){=}\frac{2m{-}n{-}1}{3}$. Hence,
$\texttt{AG}(G)=\tfrac{3}{4}\tfrac{4n-2m-2}{3}+(\tfrac{3}{\sqrt{2}}-1)+2\tfrac{2m-n-1}{3}=\tfrac{2n+5m-13}{6}+\tfrac{3}{\sqrt{2}}$.

  * •

If $2m{-}n\equiv 2\bmod{3}$, then $4n{-}2m\equiv 1\bmod{3}$, which means that
$n_{1}(G){=}\frac{4n{-}2m{-}1}{3}$, $n_{2}(G){=}0,n_{3}(G){=}1$ and
$n_{4}(G){=}\frac{2m{-}n{-}2}{3}$. Hence,
$\texttt{AG}(G)=\tfrac{3}{4}\tfrac{4n-2m-1}{3}+(\tfrac{21}{4\sqrt{3}}-\tfrac{3}{2})+2\tfrac{2m-n-2}{3}=\tfrac{2n+5m}{6}+\tfrac{21}{4\sqrt{3}}-\tfrac{37}{12}$.
∎

As shown in Table 2, if $(n,m)$ is one of the pairs for which there is a graph
$H_{n,m}$ in Figure 2 or 3, then $\texttt{AG}(H_{n,m})<U\\!B_{n,m}$. Hence,
the connected graphs in $\mathcal{G}_{n,m}$ are the only connected chemical
graphs $G$ of order $n$ and size $m$ with $\texttt{AG}(G)=U\\!B_{n,m}$. The
sharp upper bound $\texttt{AG}(H_{n,m})$ for the 22 pairs $(n,m)$ that are
exceptions is slightly smaller than $U\\!B_{n,m}$. We give in Table 2 the
values of this upper bound as well as the differences between $U\\!B_{n,m}$
and $\texttt{AG}(H_{n,m})$. We observe that the largest difference is
$\frac{1}{2}$ while the smallest is approximately equal to 0.0384.

Table 2: Sharp upper bound $\texttt{AG}(H_{n,m})$ on the arithmetic-geometric index of graphs of order $n$ and size $m$, for the 22 pairs $(n,m)$ not included in Corollary 3, and difference with $U\\!B_{n,m}$. $n$ | $m$ | $\texttt{AG}(H_{n,m})$ | $U\\!B_{n,m}-\texttt{AG}(H_{n,m})$
---|---|---|---
1 | 0 | 0 | $-\frac{11}{4}+\frac{21}{4\sqrt{3}}$ | $\approx$ | 0.2811
2 | 1 | 1 | $\frac{1}{2}$ | $\approx$ | 0.5000
3 | 2 | $\frac{3}{\sqrt{2}}$ | $\frac{1}{2}$ | $\approx$ | 0.5000
3 | 3 | 3 | $\frac{1}{2}$ | $\approx$ | 0.5000
4 | 3 | $\frac{6}{\sqrt{3}}$ | $\frac{3}{4}-\frac{3}{4\sqrt{3}}$ | $\approx$ | 0.3170
4 | 4 | $1+\frac{2}{\sqrt{3}}+\frac{5}{\sqrt{6}}$ | $\frac{3}{2}+\frac{3}{\sqrt{2}}-\frac{2}{\sqrt{3}}-\frac{5}{\sqrt{6}}$ | $\approx$ | 0.4254
4 | 5 | $1+\frac{10}{\sqrt{6}}$ | $\frac{9}{2}-\frac{10}{\sqrt{6}}$ | $\approx$ | 0.4175
4 | 6 | 6 | $-\frac{11}{4}+\frac{21}{4\sqrt{3}}$ | $\approx$ | 0.2811
5 | 5 | $\frac{7}{2}+\frac{3}{\sqrt{2}}$ | $-\frac{3}{4}-\frac{3}{\sqrt{2}}+\frac{21}{4\sqrt{3}}$ | $\approx$ | 0.1598
5 | 6 | $\frac{5}{4}+\frac{3}{\sqrt{2}}+\frac{7}{4\sqrt{3}}+\frac{5}{\sqrt{6}}$ | $\frac{13}{4}-\frac{7}{4\sqrt{3}}-\frac{5}{\sqrt{6}}$ | $\approx$ | 0.1984
5 | 7 | $1+\frac{9}{\sqrt{2}}$ | $\frac{13}{2}-\frac{9}{\sqrt{2}}$ | $\approx$ | 0.1360
5 | 8 | $2+\frac{3}{\sqrt{2}}+\frac{7}{\sqrt{3}}$ | $\frac{13}{4}-\frac{3}{\sqrt{2}}-\frac{7}{4\sqrt{3}}$ | $\approx$ | 0.1183
5 | 9 | $3+\frac{21}{2\sqrt{3}}$ | $4+\frac{3}{\sqrt{2}}-\frac{21}{2\sqrt{3}}$ | $\approx$ | 0.0591
6 | 5 | $\frac{15}{4}+\frac{3}{\sqrt{2}}$ | $\frac{1}{4}$ | $\approx$ | 0.2500
6 | 6 | $\frac{5}{2}+\frac{3}{2\sqrt{2}}+\frac{15}{4\sqrt{3}}+\frac{5}{2\sqrt{6}}$ | $\frac{9}{2}-\frac{3}{2\sqrt{2}}-\frac{15}{4\sqrt{3}}-\frac{5}{2\sqrt{6}}$ | $\approx$ | 0.2537
6 | 7 | $\frac{7}{2}+\frac{6}{\sqrt{2}}$ | $\frac{5}{4}-\frac{6}{\sqrt{2}}+\frac{21}{4\sqrt{3}}$ | $\approx$ | 0.0384
6 | 8 | $\frac{9}{2}+\frac{7}{\sqrt{3}}$ | $2+\frac{3}{\sqrt{2}}-\frac{7}{\sqrt{3}}$ | $\approx$ | 0.0799
6 | 9 | $\frac{17}{4}+\frac{3}{\sqrt{2}}+\frac{21}{4\sqrt{3}}$ | $\frac{21}{4}-\frac{3}{\sqrt{2}}-\frac{21}{4\sqrt{3}}$ | $\approx$ | 0.0976
7 | 6 | $\frac{15}{4}+\frac{4}{\sqrt{3}}+\frac{7}{4\sqrt{3}}$ | $\frac{1}{2}-\frac{1}{2\sqrt{3}}$ | $\approx$ | 0.2113
7 | 8 | $\frac{5}{2}+\frac{9}{\sqrt{2}}$ | $\frac{13}{2}-\frac{9}{\sqrt{2}}$ | $\approx$ | 0.1360
8 | 8 | $5+\frac{6}{\sqrt{2}}$ | $\frac{5}{4}-\frac{6}{\sqrt{2}}+\frac{21}{4\sqrt{3}}$ | $\approx$ | 0.0384
10 | 9 | $\frac{15}{2}+\frac{11}{2\sqrt{3}}$ | $\frac{1}{4}-\frac{1}{4\sqrt{3}}$ | $\approx$ | 0.1057

When $m=n-1$, Corollary 3 gives an upper bound for chemical trees. More
precisely, if $T$ is a chemical tree of order $n$, then

$\texttt{AG}(T)\leq
U\\!B_{n,n-1}=\frac{7n-5}{6}+\left\\{\begin{array}[]{ll}0&\mbox{\emph{if}
}n\equiv 2\bmod{3},\\\ \frac{3}{\sqrt{2}}-\frac{13}{6}&\mbox{\emph{if}
}n\equiv 0\bmod{3},\\\ \frac{21}{4\sqrt{3}}-\frac{37}{12}&\mbox{\emph{if}
}n\equiv 1\bmod{3}.\end{array}\right.$

and this bound is reached for all $n$, except for $n=1,2,3,4,6,7,10$ since
$H_{1,0},H_{2,1},H_{3,2},H_{4,3},H_{6,5},H_{7,6}$ and $H_{10,9}$ appear in
Figure 3. The same upper bound is given in [19], but the authors did not
mention the 7 exceptions. For example, they state that when $n\equiv
1\bmod{3}$, there are $\frac{n-1}{3}-1$ vertices of degree 4, and one vertex
of degree 3 that must be adjacent to vertices of degree 4. This is clearly
impossible for $n=1,4,7$ and $10$.

We now show that if we remove the constraint that extremal chemical graphs
must be connected, then no better value of AG can be obtained.

######  Theorem 2.

Let $G$ be a non-connected chemical graph of order $n$ and size $m\geq n-1$.
If $G$ is extremal, then $G$ belongs to $\mathcal{G}_{n,m}$.

###### Proof.

Assume that the theorem is not valid and let $G$ be a non-connected extremal
chemical graph of order $n$ and size $m\geq n-1$ that is a counterexample with
the smallest number of connected components. It follows from Property 2 that
$(n,m)$ is not one of the 22 pairs for which there is a graph $H_{n,m}$ in
Figure 2 or 3. Let $G_{1},\ldots,G_{k}$ ($k\geq 2$) be the connected
components of $G$, and let $N_{i}$ and $M_{i}$ be the order and the size of
$G_{i}$, respectively. Clearly,
$\texttt{AG}(G)=\sum_{i=1}^{k}\texttt{AG}(G_{i})$. Hence, since $G$ is
extremal, every $G_{i}$ is a connected extremal graph of order $N_{i}$ and
size $M_{i}$. At least one $G_{i}$, say $G_{1}$, contains a cycle $C$. If $C$
contains an edge $xy$ with $d_{x}=4$ and $d_{y}\geq 3$ then:

  * •

if $G_{2}$ contains only one vertex $z$ then let $G^{\prime}$ be the graph
obtained from $G$ by replacing the edge $xy$ by the edge $xz$. Since $y$
belongs to a cycle, at least one of its neighbors $z\neq x$ has degree at
least 2. Hence, with $i=d_{y}$, $j=d_{z}$ and $k=d_{u}$, where $u$ is any
neighbor of $y$ other than $x$ and $w$, we have

$\displaystyle\texttt{AG}(G^{\prime}){-}\texttt{AG}(G)$ $\displaystyle\geq$
$\displaystyle
c_{1,4}+\min_{i=3,4}\bigl{(}\min_{j=2,3,4}(c_{i-1,j}{-}c_{i,j})-c_{4,i}\bigr{)}$
$\displaystyle+\min_{i=3,4}\bigl{(}(i{-}2)\min_{k=1,2,3,4}(c_{i-1,k}{-}c_{i,k})\bigr{)}$
$\displaystyle\approx$ $\displaystyle 0.0193>0.$

Hence $G$ is not extremal, a contradiction.

  * •

if $G_{2}$ contains at least two vertices, then consider any edge $zw$ in
$G_{2}$ and assume without loss of generality that $d_{z}\leq d_{w}$. Let
$G^{\prime}$ be the graph obtained from $G$ by replacing the edges $xy$ and
$zw$ by the edges $xz$ and $yw$. Then, with $i=d_{y}$, $j=d_{z}$ and
$k=d_{w}$, we have

$\texttt{AG}(G^{\prime}){-}\texttt{AG}(G)\geq\min_{i=3,4}\;\min_{j=1,2,3,4}\;\min_{k=j,\ldots,4}(c_{4,j}+c_{i,k}-c_{4,i}-c_{j,k})=0.$

Moreover, all cases where $\texttt{AG}(G^{\prime})=\texttt{AG}(G)$ have
$d_{x}=d_{w}$ or/and $d_{y}=d_{z}$. Hence, $G^{\prime}$ has a smaller number
of connected components than $G$, while $n_{i}(G)=n_{i}(G^{\prime})$ for
$0\leq i\leq 4$ and $x_{i,j}(G)=x_{i,j}(G^{\prime})$ for $1\leq i\leq j\leq
4$. It follows that $G^{\prime}$ is also extremal, and either both of $G$ and
$G^{\prime}$ belong to $\mathcal{G}_{n,m}$, or none of them. If $G^{\prime}$
is connected, then we know from Theorem 1 that $G^{\prime}$ (and hence also
$G$) belongs to $\mathcal{G}_{n,m}$, which means that $G$ is not a
counterexample to the theorem, a contradiction. If $G^{\prime}$ is not
connected, then $G$ is not a counterexample to the theorem with the smallest
number of connected components, a contradiction.

Note that if $G_{1}$ belongs to $\mathcal{G}_{N_{1},M_{1}}$, then the cycle
$C$ contains two adjacent vertices of degree 4 (since vertices of degree 1 do
not belong to a cycle and there is at most one vertex of degree 2 or 3 in
$G_{1}$). Also, the 8 graphs $H_{5,6}$, $H_{5,7}$, $H_{5,8}$, $H_{5,9}$,
$H_{6,6}$, $H_{6,7}$, $H_{6,8}$, $H_{6,9}$, in Figures 2 and 3 which have a
cycle and an edge linking a vertex of degree 4 to a vertex of degree at least
3, have such an edge in a cycle. Hence, $x_{3,4}(G_{i})+x_{4,4}(G_{i})=0$ for
all connected components $G_{i}$ of $G$ with a cycle.

Suppose now that $G_{2}$ contains an edge $xy$ with $d_{x}=4$ and $d_{y}\geq
3$. Consider any edge $zw$ on $C$ and assume without loss of generality that
$d_{z}\leq d_{w}$. Let $G^{\prime}$ be the graph obtained from $G$ by
replacing the edges $xy$ and $zw$ by the edges $xz$ and $yw$. Then, with
$i=d_{y}$, $j=d_{z}$ and $k=d_{w}$, we have

$\texttt{AG}(G^{\prime}){-}\texttt{AG}(G)\geq\min_{i=3,4}\;\min_{j=2,3,4}\;\min_{k=j,\ldots,4}(c_{4,j}+c_{i,k}-c_{4,i}-c_{j,k})=0.$

As above, the only cases where $\texttt{AG}(G^{\prime})=\texttt{AG}(G)$ have
$d_{x}=d_{w}$ or/and $d_{y}=d_{z}$. Hence, either $G$ is not a counterexample
to the theorem, or it is not a counterexample with the smallest number of
connected components, a contradiction.

Hence, we know that $x_{3,4}(G)+x_{4,4}(G)=0$. We now prove that no connected
component of $G$ can have more than 9 vertices. So assume $G$ has a connected
component $H$ of order $N\geq 10$ and size $M$. We know from Theorem 1 that
there are two possible cases:

  * •

if $H$ is one of the 22 graphs in Figures 2 and 3, then $H\simeq H_{10,9}$,
which implies $x_{3,4}(G){\geq}x_{3,4}(H){=}2$, a contradiction.

  * •

if $H$ belongs to $\mathcal{G}_{N,M}$, then $n_{3}(H)=0$ else $x_{3,4}(G)\geq
x_{3,4}(H)=3$, Hence,

$x_{4,4}(H)\geq
m-n_{1}(H)-2\geq\Bigl{\lceil}m-\frac{4n-2m}{3}-2\Bigr{\rceil}=\Bigl{\lceil}\frac{5m-4n-6}{3}\Bigr{\rceil}.$

The four cases here below show that $x_{3,4}(G)+x_{4,4}(G)\geq
x_{3,4}(H)+x_{4,4}(H)\geq 1$, a contradiction.

    * –

If $M=N-1=9$ then $x_{3,4}(H)=2$.

    * –

If $M=N-1=10$, then $x_{4,4}(H)=2$.

    * –

If $M=N-1\geq 11$, then $x_{4,4}(H)\geq\lceil\frac{N-11}{3}\rceil\geq 1$.

    * –

If $M\geq N\geq 10$ then $x_{4,4}(H)\geq\frac{N-6}{3}>1$.

We thus know that $3\leq N_{1}\leq 9$, $N_{1}\leq
M_{1}\leq\min\\{2N_{1},\frac{N_{1}(N_{1}-1)}{2}\\}$ and $G_{1}$ has no edge
linking a vertex of degree 4 to a vertex of degree at least 3. It is easy to
check that there are exactly 7 such graphs, namely, $H_{3,3}$, $H_{4,4}$,
$H_{4,5}$, $H_{4,6}$, $H_{5,5}$, $H_{7,8}$ and $H_{8,8}$ (see Figures 2 and
3). Also, $1\leq N_{2}\leq 9$, $N_{2}-1\leq
M_{2}\leq\min\\{2N_{2},\frac{N_{2}(N_{2}-1)}{2}\\}$ and $G_{2}$ has no edge
linking a vertex of degree 4 to a vertex of degree at least 3. There are only
14 such graphs, namely, the 7 graphs mentioned above, and $H_{1,0}$,
$H_{2,1}$, $H_{3,2}$, $H_{4,3}$, $G_{5,4}$, $H_{6,5}$ and $G_{9,8}$ (see
Figures 1, 2 and 3).

Let $i_{n,m}$ be equal to $\texttt{AG}(G)$, where $G$ is any connected
extremal chemical graph of order $n$ and size $m$. It is easy to check by
enumeration that $i_{N_{1},M_{1}}+i_{N_{2},M_{2}}<i_{N_{1}+N_{2},M_{1}+M_{2}}$
for the 7 pairs $(N_{1},M_{1})$ and the 14 pairs $(N_{2},M_{2})$. Hence by
removing $G_{1}$ and $G_{2}$ and replacing these two connected components of
$G$ by a connected extremal chemical graph of order $N_{1}+N_{2}$ and size
$M_{1}+M_{2}$, one gets a graph $G^{\prime}$ with
$\texttt{AG}(G)<\texttt{AG}(G^{\prime})$, which means that $G$ is not
extremal, a contradiction. ∎

Corollary 2 shows that all graphs in $\mathcal{G}_{n,m}$ have the same AG
value, which means that they are all extremal if $(n,m)$ is not a pair
appearing in Figures 2 or 3. Hence, putting together Property 2 and Theorems 1
and 2, we get the following characterization of extremal chemical graphs.

######  Theorem (Characterization of extremal chemical graphs).

A chemical graph $G$ of order $n$ and size $m\geq n-1$ is extremal if and only
if $G$ is one of the 22 graphs in Figures 2 and 3 or $G$ belongs to
$\mathcal{G}_{n,m}$.

We indicate in Table 3 the number of connected and non-connected extremal
chemical graphs of order $n$ and size $m$ for $1\leq n\leq 14$ and $n-1\leq
m\leq\min\\{2n,\tfrac{n(n-1)}{2}\\}$. For example, for $n=12$ and $m=11$, we
see that there are exactly one connected and one non-connected extremal
chemical graph and these two graphs are represented at the bottom of Figure 1.
The 22 pairs $(n,m)$ for which $H_{n,m}$ is the only extremal graph are shown
in gray boxes. We observe that the number of connected extremal chemical
graphs grows exponentially, but not in a monotonic way.

The proof of Theorem 2 shows that if a non-connected chemical graph $G$
contains a cycle, then there is a chemical graph $G^{\prime}$ having fewer
connected components than $G$ and such that
$\texttt{AG}(G)\leq\texttt{AG}(G^{\prime})$. This leads to the following
corollary.

######  Corollary 4.

For all $n$ and $m$ with $0\leq m\leq n-2$ there is a chemical forest $G^{*}$
which is a disjoint union of extremal chemical trees and such that
$\emph{$\texttt{AG}$}(G)\leq\emph{$\texttt{AG}$}(G^{*})$ for all chemical
graphs $G$ of order $n$ and size $m$.

Table 3: Number of connected and non-connected extremal chemical graphs of order $n$ and size $m$ for $1\leq n\leq 14$ and $n-1\leq m\leq\min\\{2n,\tfrac{n(n-1)}{2}\\}$ | $n$
---|---
|  | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14
$m$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
0 |  | 1 | 0 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
1 |  |  |  | 1 | 0 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
2 |  |  |  |  |  | 1 | 0 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
3 |  |  |  |  |  | 1 | 0 | 1 | 0 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
4 |  |  |  |  |  |  |  | 1 | 0 | 1 | 0 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
5 |  |  |  |  |  |  |  | 1 | 0 | 1 | 0 | 1 | 0 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
6 |  |  |  |  |  |  |  | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |  |  |  |  |  |  |  |  |  |  |  |  |  |
7 |  |  |  |  |  |  |  |  |  | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |  |  |  |  |  |  |  |  |  |  |  |
8 |  |  |  |  |  |  |  |  |  | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |  |  |  |  |  |  |  |  |  |
9 |  |  |  |  |  |  |  |  |  | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |  |  |  |  |  |  |  |
10 |  |  |  |  |  |  |  |  |  | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 2 | 0 | 1 | 0 |  |  |  |  |  |
11 |  |  |  |  |  |  |  |  |  |  |  | 1 | 0 | 1 | 0 | 2 | 0 | 3 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |  |  |  |
12 |  |  |  |  |  |  |  |  |  |  |  | 1 | 0 | 2 | 0 | 4 | 0 | 2 | 0 | 4 | 0 | 6 | 0 | 2 | 0 | 1 | 0 |  |
13 |  |  |  |  |  |  |  |  |  |  |  |  |  | 2 | 0 | 3 | 0 | 10 | 0 | 12 | 0 | 4 | 0 | 5 | 1 | 7 | 1 | 2 | 1
14 |  |  |  |  |  |  |  |  |  |  |  |  |  | 2 | 0 | 8 | 0 | 17 | 0 | 8 | 1 | 21 | 1 | 23 | 1 | 5 | 1 | 3 | 1
15 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 7 | 0 | 9 | 0 | 47 | 0 | 58 | 1 | 14 | 1 | 27 | 2 | 27 | 3
16 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 6 | 0 | 37 | 0 | 77 | 0 | 31 | 1 | 113 | 2 | 111 | 4 | 18 | 2
17 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 28 | 0 | 35 | 0 | 249 | 0 | 303 | 3 | 59 | 4 | 159 | 11
18 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 16 | 0 | 198 | 0 | 399 | 0 | 134 | 2 | 684 | 8 | 625 | 20
19 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 126 | 0 | 154 | 0 | 1550 | 1 | 1786 | 9 | 298 | 11
20 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 59 | 1 | 1246 | 1 | 2395 | 1 | 707 | 7 | 4620 | 40
21 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 719 | 1 | 845 | 1 | 10801 | 4 | 11855 | 36
22 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 265 | 1 | 8789 | 3 | 16433 | 6 | 4399 | 20
23 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 4721 | 3 | 5440 | 4 | 83399 | 19
24 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 1544 | 3 | 68804 | 12 | 125829 | 28
25 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 35678 | 11 | 40399 | 14
26 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 10778 | 8 | 590342 | 55
27 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 300361 | 45
28 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 88168 | 25

##  6 Conclusion

We have determined a sharp upper bound on the value of the arithmetic-
geometric index of chemical graphs of order $n$ and size $m\geq n-1$, and we
have characterized the chemical graphs that reach the bound. This allows, for
example, to characterize extremal chemical trees as well as extremal unicyclic
or bicyclic chemical graphs. For $m\leq n-2$, we have shown that there is an
extremal chemical graph or order $n$ and size $m$ which is a disjoint union of
extremal chemical trees.

Acknowledgment: The authors would like to thank Pierre Hauweele for his help.

## References

  * [1] Aouchiche, M., Hallaoui, I. E., and Hansen, P. Geometric-arithmetic index and minimum degree of connected graphs.  Match-Communications in Mathematical and in Computer Chemistry 83, 1 (2020), 179–188.
  * [2] Bianchi, M., Cornaro, A., Palacios, J. L., and Torriero, A. Lower bounds for the geometric-arithmetic index of graphs with pendant and fully connected vertices.  Discrete Applied Mathematics 257 (2019), 53–59.
  * [3] Carballosa, W., Granados, A., Méndez Bermúdez, J. A., Pestana, D., and Portilla, A. Computational properties of the arithmetic–geometric index.  Journal of Mathematical Chemistry 60, 9 (2022), 1854–1871.
  * [4] Cui, S.-Y., Wang, W., Tian, G.-X., and Wu, B. On the arithmetic-geometric index of graphs.  arXiv preprint arXiv:2010.03748 (2020).
  * [5] Das, K., Gutman, I., and Furtula, B. Survey on geometric-arithmetic indices of graphs.  Match (Mulheim an der Ruhr, Germany) 65 (01 2011), 595–644.
  * [6] Devillez, G., Hauweele, P., and Mélot, H. Phoeg helps to obtain extremal graphs.  In Operations Research Proceedings 2018: Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), Brussels, Belgium, September 12-14, 2018 (2019), Springer Nature, p. 251.
  * [7] Diestel, R. Graph Theory, second edition ed.  Springer-Verlag, 2000.
  * [8] Gutman, I. Relation between geometric–arithmetic and arithmetic–geometric indices.  Journal of Mathematical Chemistry 59, 6 (2021), 1520–1525.
  * [9] Li, G., and Zhang, M. Sharp bounds on the arithmetic–geometric index of graphs and line graphs.  Discrete Applied Mathematics 318 (2022), 47–60.
  * [10] McKay, B. D., and Piperno, A. Practical graph isomorphism, II.  Journal of Symbolic Computation 60 (2014), 94–112.
  * [11] Milovanović, I., Matejić, M., and Milovanović, E. Upper bounds for arithmetic-geometric index of graphs.  Scientific Publications of the State University of Novi Pazar Series A: Applied Mathematics, Informatics and mechanics 10, 1 (2018), 49–54.
  * [12] Molina, E. D., Rodríguez, J. M., Sánchez, J. L., and Sigarreta, J. M. Some properties of the arithmetic–geometric index.  Symmetry 13, 5 (2021), 857.
  * [13] Niu, B., Zhou, S., and Zhang, H. Extremal arithmetic–geometric index of bicyclic graphs.  Circuits, Systems, and Signal Processing (2023), 1–22.
  * [14] Randić, M. Characterization of molecular branching.  Journal of the American Chemical Society 97, 23 (1975), 6609–6615.
  * [15] Rodríguez, J. M., and Sigarreta, J. M. Spectral properties of geometric-arithmetic index.  Applied Mathematics and Computation 277 (2016), 142–153.
  * [16] Rodríguez, J. M., Sánchez, J. L., Sigarreta, J. M., and Tourís, E. Bounds on the arithmetic-geometric index.  Symmetry 13, 4 (2021), 689.
  * [17] Shegehalli, V., and Kanabur, R. Arithmetic-geometric indices of path graph.  J. Math. Comput. Sci 16 (2015), 19–24.
  * [18] Shegehalli, V., and Kanabur, R. Arithmetic-geometric indices of some class of graph.  Journal of Computer and Mathematical sciences 6, 4 (2015), 194–199.
  * [19] Vujošević, S., Popivoda, G., Vukićević, Ž. K., Furtula, B., and Škrekovski, R. Arithmetic–geometric index and its relations with geometric–arithmetic index.  Applied Mathematics and Computation 391 (2021), 125706.
  * [20] Vukičević, D., and Furtula, B. Topological index based on the ratios of geometrical and arithmetical means of end-vertex degrees of edges.  Journal of mathematical chemistry 46 (2009), 1369–1376.
  * [21] Vukićević, Ž. K., Vujošević, S., and Popivoda, G. Unicyclic graphs with extremal values of arithmetic–geometric index.  Discrete Applied Mathematics 302 (2021), 67–75.