# A V2X-based Privacy Preserving Federated Measuring and Learning System

Levente Alekszejenkó, Tadeusz P. Dobrowiecki Department of Measurement and
Information Systems, Faculty of Electrical Engineering and Informatics,
Budapest University of Technology and Economics, Műegyetem rkp. 3., H-1111
Budapest, Hungary e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Future autonomous vehicles (AVs) will use a variety of sensors that generate a
vast amount of data. Naturally, this data not only serves self-driving
algorithms; but can also assist other vehicles or the infrastructure in real-
time decision-making. Consequently, vehicles shall exchange their measurement
data over Vehicle-to-Everything (V2X) technologies. Moreover, predicting the
state of the road network might be beneficial too. With such a prediction, we
might mitigate road congestion, balance parking lot usage, or optimize the
traffic flow. That would decrease transportation costs as well as reduce its
environmental impact.

In this paper, we propose a federated measurement and learning system that
provides real-time data to fellow vehicles over Vehicle-to-Vehicle (V2V)
communication while also operating a federated learning (FL) scheme over the
Vehicle-to-Network (V2N) link to create a predictive model of the
transportation network. As we are yet to have real-world AV data, we model it
with a non-IID (independent and identically distributed) dataset to evaluate
the capabilities of the proposed system in terms of performance and privacy.
Results indicate that the proposed FL scheme improves learning performance and
prevents eavesdropping at the aggregator server side.

###### Index Terms:

federated learning, information sharing, privacy-preserving, V2X application

##  I Introduction

While navigating through cities, autonomous vehicles (AVs) will be required to
collect and process enormous amounts of data. This data contains raw
measurement values (e.g., following distance) and derived observations (e.g.,
number of empty parking spaces on the spot). As these kinds of data further
away from the trajectory of a vehicle might be hard to obtain, it is natural
to exchange such knowledge among vehicles. The Vehicle-to-Vehicle (V2V)
communication techniques can provide a channel for this information change.
The received information might help the AVs in real-time operational (e.g.,
finding an empty parking lot) or tactical decision-making (e.g., heading
towards an area that is supposed to offer many free parking spaces).

As the collected data, especially the derived ones, describes the actual
traffic situation, AVs or even road operators shall access and process it.
This data might support strategic planning that mitigates traffic congestion
and optimizes the traffic flow (e.g., by building new parking lots or
adjusting their pricing). Consequently, we might minimize the environmental
impact of transportation. However, exchanging such enormous datasets over
Vehicle-to-Everything (V2X) networks is challenging. We assume that this
knowledge will be represented and distributed among the stakeholders (e.g.,
among AVs and road operators) as a machine learning model, e.g., the weight
matrix of a neural network. Such representation has numerous benefits: it is a
compressed extract of the data collected by the AVs, has predictive power, and
can adapt to the changes in the road network. On a Vehicle-to-Network (V2N)
channel, AVs can download the actual model from a central server and use its
predictions for tactical planning (e.g., inferring the current parking lot
occupancy rate in a neighborhood). AVs can also contribute to the training
process of this model by participating in a federated learning (FL) system.

Unfortunately, AVs only have data about a relatively small area as they can
only sense phenomena (e.g., parking lot occupancy) along their routes. Such
data necessarily forms a not independent or identically distributed (non-IID)
dataset. Non-IID data can cause performance issues and open the way for
privacy threats for the FL system. In this paper, our essential contribution
is _addressing the problem of non-IID datasets by incorporating raw data
sharing into the traditional FL scheme_ for intelligent vehicles. As a proof
of concept, we model the data of AVs by partitioning a well-known benchmark
dataset MNIST [1]. We assume raw data sharing is through a trusted (V2V)
channel, while the participants access the FL server through a separate,
untrusted (V2N) line. Based on this assumption, we demonstrate how raw data
sharing improves learning speed and mitigates privacy issues.

###  I-A Related Works

It will be vital to use V2X communication to exploit the merits of AVs.
Connected vehicles can implement platoons and minimize the following distance
[2, 3], or make it possible to improve intersection management [4]. As the V2X
channel bandwidth is limited, we shall consider how to reduce the number of
exchanged data packages. According to [5], channel usage can be optimized by
estimating and maximizing the information gains over the observations. This
approach is theoretically related to the one described in this paper, but
here, we aim to balance the datasets of the AVs to mitigate the effects of
non-IID data.

Despite the numerous security mechanisms of V2X communication [6], handling
non-IID data on the application level is still an important issue. The non-IID
nature of the data might disclose information about a vehicle’s route
revealing the origins and destinations of the passengers. In the case of
commercial vehicles, that would mean that the whole supply chain of a company
might be exposed. To mitigate this problem, there are both low-level
solutions, such as using pseudonyms [7, 6] and certificates [6], as well as
application-level solutions, e.g., maximizing the location entropy in social
internet of vehicle applications [8].

The abovementioned solutions require a trusted third (or even fourth) party.
Federated learning [9], that has gained popularity recently, may provide a
simpler solution by an adoption to the vehicular domain. However, FL needs to
exchange data periodically, which might be challenging in V2X communication;
[10] proved that FL works even in poor networking conditions. Although
multiple papers [10, 11] refer to FL as a privacy-protecting scheme, the
survey in [12] demonstrates how difficult it might be to secure an FL system.
Most of the privacy-preserving FL mechanisms build on either distorting the
data or classical cryptographic approaches that might be vulnerable to quantum
computer algorithms. Considering the long lifespan of a vehicle or a piece of
infrastructural equipment, we shall consider the post-quantum cryptography
problem, which might be impossible with traditional solutions according to the
survey of [6]. FL has vulnerabilities against either active or passive attacks
in the V2X domain. While [13] mitigates the impact of an active attack against
the FL system; in this study, as an elaboration of our concept [14, 15], we
focus on a passive eavesdropping attack against an FL scheme at a V2N server
side and its prevention by trusted V2V communication.

The rest of the paper is organized as follows: In Section II, we introduce the
fundamental idea of a V2X-based, privacy-aware FL scheme. After that, Section
III presents the evaluation of the proposed learning scheme. In Section III-A,
we describe how partitioning the MNIST data models obtained data of commuting
AVs. Our key contribution is Section III-B, which focuses on training data
sharing among AVs. For numerical evaluation, Section III-C defines different
measurement setups and Section III-D elaborate the technical details of the
training process. The defined measurement setups are compared by their
learning performance in Section III-E, and by their privacy-awareness in
Section III-F. Lastly, Section IV concludes this paper.

##  II System Architecture

The principal assumption for our work is an extensive V2V information exchange
between the vehicles. AVs can use the received data in real-time operational
decision-making. Moreover, the retrieved knowledge (along with an AV’s own
measurements) can serve as training data for machine learning mechanisms. As
V2V implementations are usually direct connections between two vehicles, we
assume this channel is trusted and secure.

On the other hand, the community of AVs might measure some phenomena, e.g.,
congestion levels or occupancy rate of parking lots, that are beneficial to
improve the traffic flow. Intelligent traffic controller systems, or even AVs
can exploit the merits of such knowledge encapsulated in a queryable
predictive model. To build such a model, we propose a vehicular FL system. The
aggregator server of this system shall reside in the cloud, see Fig. 1, and
the _participant_ AVs shall connect to this server via V2N solutions and
download the actual federated model. Additionally, the server can request a
subset of the available AVs to train their local model and upload their
updated weight matrix. The server runs a FedAvg [9] algorithm to create the
next version of the federated model.

As the link between the AVs and the cloud is indirect, including, e.g.,
routers and switches, we might not safely assume that this link is secure. To
prevent a successful eavesdropping attack against the vehicular FL system, we
propose that AVs use their measurement data together with the information
received over the V2V communication to moderate their non-IID characteristics.
We expect this will improve the speed of the training process by potentially
utilizing more data. Also, in this way, by reducing the non-IID nature of the
training data of the participant AVs, it will lower the probability of a
successful cyber attack. (It may also attenuate the bias of the optimal global
model, but this problem is out of the scope of this paper.)

Figure 1: Illustration of the FL setup. Participant AVs can communicate with
each other and the server. Participants can share data on a trusted V2V link,
while the server receives and sends the model parameters of the FL process on
an untrusted V2N channel.

##  III Evaluation

To evaluate the proposed FL system, we implemented a small model consisting of
10 participants (that represent the AVs) and an aggregation server. Whenever
the server initiated a communication round, the participants exchanged a part
of their training datasets (modeling the V2V communication). Then, each of the
10 participants ran exactly 1 epoch of training. Finally, the participants
uploaded their new weight matrix to the server that aggregates the result by a
FedAvg algorithm. Through this process, we can assess the learning process at
a fine-grained level.

###  III-A Data Modeling

As it is a commonly used dataset in FL [9], in adversarial machine learning
literature [16], and in the automotive or transportation domain [10, 13, 17,
18, 19], we used the MNIST [1] dataset in the modeled training process. MNIST
consists of hand-written digits (as $28\times 28$ sized matrices) as input
features, and the objective is to identify the corresponding digit as a
10-class classification problem.

As non-IID data is the primary source of privacy issues, we partitioned the
MNIST dataset into 10 parts. Each partition contained half of the samples
belonging to a particular digit, and we distributed the remaining records of
this digit randomly among the other 9 participants following a uniform
distribution. This results in 10 non-IID datasets (of about the same size),
and within each of these parts, there is a specific _overrepresented_ class
label (a particular digit), see Fig. 2(c). The 10 modeled participants got
these 10 non-IID datasets as training data (with approximately 5421 samples
each111The entire MNIST dataset contains approximately 60000 samples; however,
digit 5 only has 5421 samples. Consequently, we used only 5421 samples from
each digit label.). Consequently, without balancing their datasets, every
participant recognizes its overrepresented digit more accurately than the
other numbers.

(a) A vehicle commutes from the suburb to the city center along Avenue 1.
During its movement, the vehicle measures a phenomenon in certain sensor range
(dashed circle).

(b) Consequently, the vehicle 1 will have many data from Avenue 1, and only a
few from other avenues (from the black lines).

(c) Dataset possessed by a participant. By partitioning the MNIST dataset, we
can model the non-IID nature of the data of commuting vehicles.

Figure 2: Modeling commuting vehicles’ data by partitioning the MNIST dataset.

We consider this is an abstract model of a real-world scenario where 10
different cars commute from a suburb to the city center222The mentioned
partitioning corresponds to a situation, e.g., when one commutes from the
suburban town of Érd to the Inner City of Budapest, capital of Hungary. Then,
in the city center, one moves in the 5–8th Districts as well as in the 14th
District of Budapest. along separate avenues and measure a phenomenon within a
defined range, see Fig. 2(a) and measure data only in a specific part of the
city (along their routes). As a result, the commuters will know their
corresponding avenue well; therefore, measurements from their route form an
overrepresented class in their dataset, see Fig. 2(b). Meanwhile, they will
have only limited knowledge about the other parts of the city.

###  III-B Data Sharing

V2V data sharing is the prerequisite for operating the system described in
Section II. We assume that such communication technologies will have a limited
range; therefore, in the modeled situation, vehicles can exchange data when
they are close to each other, e.g., in the city center. We also wanted to
model that AVs’ recent measurements form possibly only a small dataset.
Consequently, a small to-be-sent dataset was calculated for each vehicle in
every communication round (simulated day, see Section III-D). Then, the AVs
transmitted this _to-be-sent_ dataset to each of the other 9 vehicles.

When the AVs get into communication range, they shall pick a piece of their
raw data for sending. However, the exchanged raw data can also be an input for
real-time decision-making; this aspect is out of the scope of the current
paper. Hence, we assume that each record is equally important, and the
vehicles can sample their data randomly upon knowledge exchange. This way, we
aimed to balance each participant’s dataset to be more IID and to test its
effect on the proposed FL system.

To this end, we calculate how many samples from a digit category an AV shall
receive from other vehicles in the beginning of each FL communication round.
Let denote the number of digit categories as $n_{c}$, the number of
participants as $n_{p}$, and the number of samples possessed by a participant
from a given $i$ data class as $n_{s,i}$. Moreover, $p$ will be the rate of
overrepresentation; i.e., the number of samples in the $o$ overrepresented
class $n_{s,o}$ divided by the number of total records of the participant
$\sum_{i=1}^{n_{c}}n_{s,i}$:

$p=\frac{n_{s,o}}{\sum_{i=1}^{n_{c}}n_{s,i}}.$ (1)

E.g., the data partitioning mentioned in Section III-A results in $p=0.5$
overrepresentation rate. Using this notation, we can compute the $x$ number of
samples belonging to each digit that an AV shall receive from all other
participants to enhance the population of the underrepresented digit classes,
and to make the AV’s training dataset IID:

$\frac{n_{s}(1-p)}{n_{c}-1}+(n_{p}-1)x=\frac{n_{s}}{n_{c}}.$ (2)

On the left-hand side of eq. (2), the first summand expresses the number of
samples that a vehicle possesses (from an underrepresented class). The second
term describes the number of samples that shall be received over V2V
communication, and the right-hand side ensures the IID nature by a uniform
distribution. Solving eq. (2) for an integer $x$ with the parameters of Table
I, yields $x=27$. Consequently, each vehicle shall share $27$ samples from
each digit category. As they have at least approx. $301$ records of each
digit, they can choose $27$ out of it.

A higher $p$ indicates a less IID dataset (in our experiments, $p=0.1$
corresponds to the IID case, see Section III-C). Consequently, a higher $p$
would require more samples to share indicated by a higher $x$ value. At
$p=1.0$, a participant would only possess samples from one data class, which
would even make it impossible to run the data sharing method.

TABLE I: Parameters to balance the AVs’ data parameter | description | value
---|---|---
$n_{s}$ | #samples per category | $5421$
$n_{c}$ | #categories | $10$
$p$ | overrepresentation rate | $0.5$
$n_{p}$ | #participants | $10$

###  III-C Measurement Cases

The original FL scheme performs well on non-IID parts built from the MNIST
dataset [9]. Consequently, we suspect that raw data sharing will further
improve the performance of the FL approach. In this section, we evaluate the
learning performance of the proposed system.

To assess the merits of the proposed FL scheme enhanced by _data exchange_ ,
we will compare its capabilities to the following traditional approaches:

  * •

_Centralized learning (baseline):_ We trained a single convolutional neural
network that uses the whole MNIST dataset for training.

  * •

_FL with IID data (IID):_ We trained an original federated setup in which the
participants had IID partitions of the MNIST dataset representing the
idealistic data distribution of a federated system.

  * •

_FL with non-IID data (non-IID):_ Without utilizing the V2V real-time data
sharing, AVs are assumed to have non-IID data from a traffic phenomenon. To
model this case, we trained a federated system with the non-IID ($p=0.5$)
partitioning of the MNIST dataset described in Section III-A.

###  III-D Training Process

To analyze how the training dataset distribution influences the model
performance, the same $p=0.5$ MNIST partitioning was used for each FL
measurement. We trained a simple convolutional neural network (CNN) described
in [20] within each experiment333We used the stochastic gradient descent (SGD)
optimizer, and the hyperparameters were fixed: The learning rate was $0.01$,
and the momentum was $0.9$.. In the beginning, the weight matrix of the neural
network was randomly initialized. To cope with the stochastic nature of neural
network training, we repeated every measurement 10 times.

We used PyTorch to implement the CNN, while Flower [21] provided the framework
for FL. Execution of the FL processes proceeds as follows:

  1. 1.

In case of the _data exchange_ measurements, each participant samples its to-
be-sent $n_{c}\times x=10\times 27$ records (27 samples for each of the 10
digits) from its knowledge base. Then, the participants exchange among each
other these to-be-sent datasets.

  2. 2.

To make a fine-grain evaluation possible, each participant trains its CNN for
exactly 1 epoch. In the case of _data exchange_ , their training data is a
mixture of their original partition and the received data; otherwise, they
might only use their own MNIST portion.

  3. 3.

The participants send their updated model to the server of the FL system.

  4. 4.

The server aggregates the results with the FedAvg method.

  5. 5.

The server re-sends the updated model to the participants.

In every measurement, we trained the CNN for 500 epochs.

The described training process models AVs departing from the suburbia in the
morning and commuting to the city center. During their movements, they meet
other AVs, with whom they share some information (gathered last evening and
this morning) over a V2V communication solution. In the evening, the AVs
return home; then, at night (e.g., while on charger), they train their CNN and
send the model updates to the aggregating server over a V2N channel. Then, in
the morning, the AVs can pull the latest federated model version from the
service provider.

If a concrete use case required it, we would be able to increase the frequency
of the FL rounds. A natural upper bound to this frequency is the frequency of
meetings of AVs on the road.

###  III-E Performance Evaluation

For evaluation, we will use the entire MNIST dataset (containing
$m_{i}=10\times 5421$ samples1). This approach models a powerful attacker who
is assumed to have access to all training data and whose goal is to identify
what is the overrepresented class of an FL participant.

Figure 3: Test accuracy of the learning methods when reaching convergence,
average of 10 measurements.

To evaluate the learning capabilities of the different measurement cases, we
define validation _accuracy_ $a_{i}$ as rate of the $r_{i}$ number of
successfully recognized samples over the number of used test samples $m_{i}$
after the $i$th training run $a_{i}=\frac{r_{i}}{m_{i}}$.

Now, we can measure the _convergence speed_ (CS) as a relative metric based on
the accuracy. We compare the FL setup accuracy (the accuracy provided by the
global, aggregated model) to the baseline case: CS is the first training round
when the given method’s accuracy falls within at least 95% of the baseline
accuracy. Thus, a lower CS value indicates that a learning process is faster.

Moreover, it is also crucial to check how accurate a FL system can be. To this
end, we also measured the _maximal accuracy_ (MA) for each measurement case.
To mitigate the effect that the used CNN model might not fit the data
perfectly, we publish MA values as the rate of the $\max_{i}a_{i}$ maximal
accuracy over the maximal accuracy $\max_{i}a_{b,i}$ achieved by the baseline,
centralized model as defined:

$\text{MA}=\frac{\max_{i}a_{i}}{\max_{i}a_{b,i}}.$ (3)

In Table II, we summarize the achieved performance parameters.

TABLE II: Learning performance of the federated, global models; and security evaluation of model updates, success rate of an honest-but-curious attacker at the server side. Average of 10 measurements. | _learning performance_ | _adversarial performance_
---|---|---
_method_ | CS | MA | R
`IID` | $143$ | $98.77\%$ | 1.0
`non-IID` | $163$ | $98.45\%$ | 10.0
`data exchange` | $143$ | $98.65\%$ | 1.1

According to Fig. 3 and Table II, data exchange improves the CS making the
proposed system as fast as an ideal FL system, in which the participants
possess IID distributed data portions, outperforming the non-IID system by
approximately 14% in CS. In the MA metric, the IID case is slightly better
than the data exchanging and the non-IID approaches, but the differences are
negligible.

###  III-F Privacy Threats

Balancing the participants’ datasets to be IID is beneficial for learning
performance; however, the V2V data exchange might also function as a privacy-
preserving technique for the FL.

Tracking a vehicle in the road network is unquestionably a privacy risk.
Successful trackings may yield significant financial benefits or provide
important intelligence reports. Considering the possible information gain, the
technical challenges and the costs of such an attack, we can assume that the
_attacker_ resides on the federated server side. Using the taxonomy of [12],
we assume this attacker to be a passive, honest-but-curious attacker whose
goal is to supply surveillance reports without disturbing the FL system. The
attacker can eavesdrop on the V2N communication between the vehicles and the
central federating learning server; hence, it accesses the reported model
weight updates in the training phase.

For the evaluation, the attacker has access to the entire MNIST dataset. It is
an unrealistic scenario, justified by the idea that if we can show that the
proposed method preserves privacy even against such a strong attacker, it can
also provide privacy in a more natural case.

The attacker aims to track a vehicle, i.e., in our model, to infer a
participant’s overrepresented data class. Hence, it presumes that the non-IID
training dataset will result in a biased local model. Such a model predicts
values from its overrepresented class more accurately, and its prediction
accuracy is reduced in other parts of the feature space. Exploiting this
assumption, the attacker evaluates the prediction accuracy of a participant’s
model described by the received weight updates as follows:

  1. 1.

The attacker samples $\mathcal{S}_{0},\mathcal{S}_{1},\dots\mathcal{S}_{9}$
evaluating records from the whole MNIST datasets for each corresponding digit.

  2. 2.

Given participant model $M$, the attacker calculates which is the most
accurately predicted class on the average:
$\hat{o}=\arg\max_{i}\bar{a}(M(\mathcal{S}_{i}))$, where
$\bar{a}(M(\mathcal{S}_{i}))$ refers to the mean accuracy of the $M$ model on
the $\mathcal{S}_{i}$ class.

  3. 3.

The attacker assumes that the participant had digit $\hat{o}$ as its
overrepresented class.

In our experiments, we had 10 participants (ParticipantA, ParticipantB, …,
ParticipantJ) that possessed digit 0, digit 1, …, digit 9 as
$o_{1},o_{2},~{}\dots,~{}o_{10}$ overrepresented classes respectively. Let $R$
be the success rate of the attacker be measured as the number of correctly
identified overrepresented classes $\sum_{i}I(o_{i}=\hat{o}_{i})$, where
$I(\cdot)$ stands for the indicator function being $1$ if its argument is true
and $0$ otherwise. The attacker has a
$p_{s}=\mathbb{P}(o=\hat{o})=\frac{1}{n_{c}}=\frac{1}{10}$ chance to correctly
identify the overrepresented class of a participant by random guessing in a
single attack. Assuming the independence of the $n_{a}=10$ attacks this
process (following a binomial distribution) would result in an $R=n_{a}\cdot
p_{s}=1.0$ expected success rate.

(a) In 9 of the 10 training rounds the attacker cannot identify the
overrepresented classes of the participants. An example of the usual
performance of the attacker.

(b) In 1 of the 10 training rounds the attacker might be more successful in
identifying the overrepresented classes of the participants. An example of the
best performance of the attacker.

Figure 4: Most accurately recognized overrepresented classes by the attacker.
Results corresponds to single training processes with each method.

Consequently, any $R\leq 1.0$ indicates that the attacker is not more
successful than random guessing, meaning that the participants (i.e., their
weight updates) are algorithmically not distinguishable, even by an
unnaturally strong attacker. As algorithmic indistinguishability is the
general definition of security, we can consider an $R\leq 1.0$ process to be
secure.

Table II together with Fig. 4 summarizes the security evaluation results. The
ideal IID case is secure by nature, and the attacker can only identify that
participantA possesses the most samples of digit 0. This identification is
only accidental (digit 0 turns to be the best estimate for each participant).
The non-IID case, which corresponds to the traditional FL approach, is
surprisingly revealing and has an $R=10$ success. According to our
experiments, incorporating measurement data from V2V communication into the
training data sets of the participants helps to preserve users’ privacy
because the resulting process behaves almost identically (providing $R=1.1$
success without certainly distinguishing the participants) to the ideal IID
one. Hence, such an attacker fails to firmly identify the overrepresented
classes of the participants.

##  IV Conclusion

In this paper, we proposed a federated measuring and learning system
architecture that utilizes the capabilities of V2X communication. Within this
system, fellow vehicles share real-time information on V2V channels. In the
meantime, the AVs train a federated machine learning model and communicate
with a central aggregating server by V2N techniques. We propose that the AVs
shall incorporate the real-time data exchanged on V2V into their training
dataset to make it more independently and identically distributed. By adopting
a benchmark machine learning problem, the handwritten digit recognition on the
MNIST dataset, we provided experimental results that the _proposed learning
scheme improves the learning performance and, at the same time, mitigates the
possible passive eavesdropping attacks against private information_ in V2X
communication systems.

###  IV-A Discussion

To prove the security of the learning setup, we had to assume a powerful,
honest-but-curious attacker on the FL site aiming to track the vehicles. In
our experiment, this attacker had access to the entire training dataset, which
is an unrealistic worst-case scenario. Moreover, the $p=0.5$ MNIST
partitioning provided articulated non-IID nature of the training data444Real-
world or simulated vehicular datasets would add random noise to the
distribution of records by nature: Traffic congestion modifies recording
times. Depending on a concrete road network, realistic, traffic equilibria-
based routing algorithms may provide various routes.. We showed that despite
such an advantage, in the majority of the cases, the attacker cannot
distinguish the proposed solution (with raw-data exchanging participants) from
an ideal one (with participants having IID data), which indicates that our
approach can mitigate privacy threats against weaker and more realistic
attackers.

Moreover, there are various FL aggregation algorithms that handle data
heterogeneity (e.g., FedProx [22], SCAFFOLD [23], FedNova [24]) and enhance
model accuracy; but these methods do not guarantee privacy-preservation
assuming the attacker can eavesdrop on the communication between the
participants and the aggregator server. Hence, in this paper, we focused on
alleviating the privacy threats at their origin by balancing the training
datasets to have an IID nature.

Although, in Section III-B, we sketched a simple data-sharing method; in real-
world scenarios, to-be-sent data sets (with sample prioritization and handling
of missing data) are harder to select. When calculating such a dataset, the
sender might focus on achieving the highest possible data utility to provide
information for the real-time decision algorithms of the receiver. However, in
the meantime, the sender shall keep its private information hidden while
minimizing also the usage of the communication channel. Solving these
competing interests is a challenging task. In the future, our research will
focus on solving this problem.

In this paper, the proposed learning system was illustrated by an application
in the intelligent transportation domain. However, with proper adaption, it
might be applied in different fields of study. To encourage experimentation
and for further development, our source codes are publicly available on
GitHub: https://github.com/alelevente/FeLeSh.

## Acknowledgment

Project no. TKP2021-EGA-02 has been implemented with the support provided by
the Ministry of Culture and Innovation of Hungary from the National Research,
Development and Innovation Fund, financed under the TKP2021-EGA funding
scheme. The project was also supported by the European Union project
RRF-2.3.1-21-2022-00004 within the framework of the Artificial Intelligence
National Laboratory. Supported by the ÚNKP-23-3-II-BME-233 New National
Excellence Program of the Ministry for Culture and Innovation from the source
of the National Research, Development and Innovation Fund.

## References

  * [1] Y. Lecun, L. Bottou, Y. Bengio and P. Haffner  “Gradient-based learning applied to document recognition”  In _Proc. of the IEEE_ 86.11, 1998, pp. 2278–2324  DOI: 10.1109/5.726791
  * [2] Swaroop Darbha, Shyamprasad Konduri and Prabhakar R. Pagilla  “Benefits of V2V Communication for Autonomous and Connected Vehicles”  In _IEEE Trans. on Intelligent Transportation Systems_ 20.5, 2019, pp. 1954–1963  DOI: 10.1109/TITS.2018.2859765
  * [3] Anis Boubarki and Sonia Mettali Gammar  “Intra-Platoon Communication in Autonomous Vehicle: A survey”  In _2020 9th IFIP Int. Conf. on Performance Evaluation and Modeling in Wireless Networks (PEMWN), Dec. 1–3, 2020, Berlin, Germany_ , pp. 1–6  DOI: 10.23919/PEMWN50727.2020.9293086
  * [4] Elnaz Namazi, Jingyue Li and Chaoru Lu  “Intelligent Intersection Management Systems Considering Autonomous Vehicles: A Systematic Literature Review”  In _IEEE Access_ 7, 2019, pp. 91946–91965  DOI: 10.1109/ACCESS.2019.2927412
  * [5] Takamasa Higuchi et al.  “Value-Anticipating V2V Communications for Cooperative Perception”  In _2019 IEEE Intelligent Vehicles Symposium (IV)_ , 2019, pp. 1947–1952  DOI: 10.1109/IVS.2019.8814110
  * [6] Takahito Yoshizawa et al.  “A Survey of Security and Privacy Issues in V2X Communication Systems”  In _ACM Comput. Surv._ 55.9 New York, NY, USA: Association for Computing Machinery, 2023  DOI: 10.1145/3558052
  * [7] Ruqayah Al-ani, Thar Baker, Bo Zhou and Qi Shi  “Privacy and safety improvement of VANET data via a safety-related privacy scheme”  In _International Journal of Information Security_ , 2023  DOI: 10.1007/s10207-023-00662-6
  * [8] Ling Xing et al.  “Location Entropy-Based Privacy Protection Algorithm for Social Internet of Vehicles”  In _Wireless Personal Communications_ Springer ScienceBusiness Media LLC, 2023  DOI: 10.1007/s11277-023-10413-4
  * [9] H. Brendan McMahan et al.  “Communication-Efficient Learning of Deep Networks from Decentralized Data”  In _Proc. of the 20th Int. Conf. on Artificial Intelligence and Statistics (AISTATS) 2017._ 54 Fort Lauderdale, FL, USA: PMLR, 2017, pp. 1273–1282
  * [10] Rui Song et al.  “Federated Learning Framework Coping with Hierarchical Heterogeneity in Cooperative ITS”  In _2022 IEEE 25th Int. Conf. on Intelligent Transportation Systems (ITSC)_ , 2022, pp. 3502–3508  DOI: 10.1109/ITSC55140.2022.9922064
  * [11] Ge Wang, Fangmin Xu, Hengsheng Zhang and Chenglin Zhao  “Joint resource management for mobility supported federated learning in Internet of Vehicles”  In _Future Generation Computer Systems_ 129, 2022, pp. 199–211  DOI: 10.1016/j.future.2021.11.020
  * [12] Xuefei Yin, Yanming Zhu and Jiankun Hu  “A Comprehensive Survey of Privacy-Preserving Federated Learning: A Taxonomy, Review, and Future Directions”  In _ACM Computing Surveys, July 2022,_ 54.6, 2021, pp. 1–36  DOI: 10.1145/3460427
  * [13] Waleed Yamany, Nour Moustafa and Benjamin Turnbull  “OQFL: An Optimized Quantum-Based Federated Learning Framework for Defending Against Adversarial Attacks in Intelligent Transportation Systems”  In _IEEE Trans. on Intelligent Transportation Systems_ 24.1, 2023, pp. 893–903  DOI: 10.1109/TITS.2021.3130906
  * [14] Levente Alekszejenkó and Tadeusz P. Dobrowiecki  “The Conceptual Framework of a Privacy-Aware Federated Data Collecting and Learning System” doi: 10.3311/MINISY2022-013 In _Proc. of the 29th MINISY@DMIS, Budapest, Hungary, Feb. 7–8, 2022_ , 2022, pp. 50–53
  * [15] Levente Alekszejenkó and Tadeusz Dobrowiecki  “Towards an Efficient, Privacy-aware Federated Learning Scheme” Preprint (Version 1) available at Research Square; doi: 10.21203/rs.3.rs-2072660/v1, 2022
  * [16] Adnan Qayyum, Muhammad Usama, Junaid Qadir and Ala Al-Fuqaha  “Securing Connected & Autonomous Vehicles: Challenges Posed by Adversarial Machine Learning and the Way Forward”  In _IEEE Communications Surveys & Tutorials_ 22.2, 2020, pp. 998–1026  DOI: 10.1109/COMST.2020.2975048
  * [17] Jin-Hua Chen, Min-Rong Chen, Guo-Qiang Zeng and Jia-Si Weng  “BDFL: A Byzantine-Fault-Tolerance Decentralized Federated Learning Method for Autonomous Vehicle”  In _IEEE Trans. Veh. Technol._ 70.9, 2021, pp. 8639–8652  DOI: 10.1109/TVT.2021.3102121
  * [18] Ahmad Hammoud, Azzam Mourad, Hadi Otrok and Zbigniew Dziong  “Data-Driven Federated Autonomous Driving”  In _Mobile Web and Intelligent Information Systems_ , Lecture Notes in Computer Science  Cham: Springer Int. Pub., 2022, pp. 79–90  DOI: 10.1007/978-3-031-14391-5“˙6
  * [19] Michael Kamp et al.  “Efficient Decentralized Deep Learning by Dynamic Model Averaging”  In _Machine Learning and Knowledge Discovery in Databases_ , Lecture Notes in Computer Science  Cham: Springer Int. Pub., 2019, pp. 393–409  DOI: 10.1007/978-3-030-10925-7“˙24
  * [20] G. Koehler, A. Amantini and P. Markovics  “MNIST Handwritten Digit Recognition in PyTorch” [Online, accessed 12-September-2022], 2020  URL: https://nextjournal.com/gkoehler/pytorch-mnist
  * [21] Daniel J Beutel et al.  “Flower: A Friendly Federated Learning Research Framework”  In _arXiv preprint_ , 2020  DOI: 10.48550/arXiv.2007.14390
  * [22] Tian Li et al.  “Federated Optimization in Heterogeneous Networks”  In _arXiv preprint_ , 2020  DOI: 10.48550/arXiv.1812.06127
  * [23] Sai Praneeth Karimireddy et al.  “SCAFFOLD: Stochastic Controlled Averaging for Federated Learning”  In _arXiv preprint_ , 2021  DOI: 10.48550/arXiv.1910.0637
  * [24] Jianyu Wang et al.  “A Novel Framework for the Analysis and Design of Heterogeneous Federated Learning”  In _IEEE Trans. on Signal Processing_ 69, 2021, pp. 5234–5249  DOI: 10.1109/TSP.2021.3106104


# Spectral extremal graphs for edge blow-up of star forests ††thanks: Research
was partially supported by the National Nature Science Foundation of China
(grant numbers 11871329, 11971298, 1220010800) and Hainan Provincial Natural
Science Foundation of China (No. 122QN218)

Jing Wang1 Zhenyu Ni2 Liying Kang3 Yi-zheng Fan
1College of Mathematics and Information Science, Henan Normal University,
Xinxiang 453007, P.R. China
2Department of Mathematics, Hainan University, Haikou 570228, P.R. China
3Department of Mathematics, Shanghai University, Shanghai 200444, P.R. China
4 School of Mathematical Sciences, Anhui University, Hefei 230601, P. R. China
Corresponding author. Email address<EMAIL_ADDRESS>(L. Kang),
wj517062214@163.com(J. Wang), 1051466287@qq.com(Z. Ni), fanyz@ahu.edu.cn(Y.
Fan)

###### Abstract

The edge blow-up of a graph $G$, denoted by $G^{p+1}$, is obtained by
replacing each edge of $G$ with a clique of order $p+1$, where the new
vertices of the cliques are all distinct. Yuan [J. Comb. Theory, Ser. B, 152
(2022) 379–398] determined the range of the Turán numbers for edge blow-up of
all bipartite graphs and the exact Turán numbers for edge blow-up of all non-
bipartite graphs. In this paper, we prove that the graphs with the maximum
spectral radius in an $n$-vertex graph without any copy of edge blow-up of
star forests are the extremal graphs for edge blow-up of star forests when $n$
is sufficiently large.

Keywords: Spectral radius; Edge blow-up; Spectral extremal graph

AMS (2000) subject classification: 05C50; 05C35

##  1 Introduction

Given a simple graph $G=(V(G),E(G))$, let $\delta(G)$ and $\Delta(G)$ be its
minimum and maximum degrees of $G$, respectively. We use $e(G)$ to denote the
number of edges in $G$. For $V_{1},V_{2}\subseteq V(G)$, $E(V_{1},V_{2})$
denotes the set of edges between $V_{1}$ and $V_{2}$, and
$e(V_{1},V_{2})=|E(V_{1},V_{2})|$. For any $S\subseteq V(G)$, let
$N(S)=\cup_{u\in S}\\{v:uv\in E(G)\\}$, $d_{S}(v)=|N_{S}(v)|=|N(v)\cap S|$.
$G\setminus S$ denotes the graph obtained from $G$ by deleting all vertices in
$S$ and their incident edges. $G[S]$ denotes the graph induced by $S$ whose
vertex set is $S$ and whose edge set consists of all edges of $G$ which have
both ends in $S$. A set $M$ of disjoint edges of $G$ is called a matching in
$G$. The matching number, denoted by $\nu(G)$, is the maximum cardinality of a
matching in $G$. We call a matching with $k$ edges a $k$-matching, denoted by
$M_{k}$. For two vertex disjoint graphs $G$ and $H$, the union of $G$ and $H$,
denoted by $G\cup H$, is the graph with vertex set $V(G)\cup V(H)$ and edge
set $E(G)\cup E(H)$. The join of $G$ and $H$, denoted by $G\vee H$, is the
graph obtained from $G\cup H$ by adding all edges between $V(G)$ and $V(H)$.
$K_{r}$ denotes the complete graph of order $r$. Let
$K_{r}(n_{1},\cdots,n_{r})$ be the complete $r$-partite graph with classes of
sizes $n_{1},\cdots,n_{r}$. If $\sum_{i=1}^{r}n_{i}$ $=n$ and
$|n_{i}-n_{j}|\leq 1$ for any $1\leq i<j\leq r$, then
$K_{r}(n_{1},\cdots,n_{r})$ is called an $r$-partite Turán graph, denoted by
$T_{r}(n)$. Let $S_{k}$ be a star of $k$ edges. The center of a star is the
vertex of maximum degree in the star. A star forest is the union of vertex
disjoint stars. We use $S_{k_{1},\cdots,k_{q}}$ to denote
$\cup_{i=1}^{q}S_{k_{i}}$, where $k_{1}\geq k_{2}\geq\cdots\geq k_{q}\geq 1$.

Given a family of graphs $\mathcal{F}$, a graph $G$ is called
$\mathcal{F}$-free if it does not contain any copy of $F$ in $\mathcal{F}$. If
$\mathcal{F}=\\{F\\}$, we use $F$-free instead of $\mathcal{F}$-free. In 1941,
Turán [18] proved that if $G$ is $K_{r+1}$-free of order $n$, then $e(G)\leq
e(T_{r}(n))$, with equality if and only if $G=T_{r}(n)$. The problem of
determining the maximum number of edges among all $n$-vertex
$\mathcal{F}$-free graphs is usually called the Turán type extremal problem.
The Turán number, denoted by $\mathrm{ex}(n,\mathcal{F})$, is the maximum
number of edges among all $n$-vertex $\mathcal{F}$-free graphs. An $n$-vertex
$\mathcal{F}$-free graph with $\mathrm{ex}(n,\mathcal{F})$ edges is called an
extremal graph for $\mathcal{F}$. Denote by $\mathrm{Ex}(n,\mathcal{F})$ the
set of all extremal graphs for $\mathcal{F}$.

Given a graph $G$ and an integer $p\geq 2$, the edge blow-up of $G$, denoted
by $G^{p+1}$, is obtained by replacing each edge of $G$ with a clique of order
$p+1$, where the new vertices of the cliques are all distinct. Simonovits [16]
and Moon [10] determined the extremal graphs for the edge blow-up of
matchings. Chen, Gould, Pfender and Wei [1] determined the Turán number for
the edge blow-up of stars. There are other extremal results for the edge blow-
up of paths, cycles and trees, see [6, 9, 19, 11]. In 2022, Yuan [21]
determined the range of the Turán numbers for edge blow-up of all bipartite
graphs and the exact Turán numbers for edge blow-up of all non-bipartite
graphs.

The spectral radius of a graph $G$ is the spectral radius of its adjacent
matrix $A(G)$, denoted by $\rho(G)$. In 2010, Nikiforov [15] proposed the
following spectral Turán type extremal problem: What is the maximum spectral
radius among all $n$-vertex $\mathcal{F}$-free graphs? We denote by
$\mathrm{Ex_{sp}}(n,F)$ the set of all graphs which attain the maximum
spectral radius. Nikiforov [13] determined the spectral version of Turán’s
extremal result, and proved that if $G$ is a $K_{r+1}$-free graph on $n$
vertices, then $\rho(G)\leq\rho(T_{r}(n))$, with equality if and only if
$G=T_{r}(n)$. Cioabă, Feng, Tait and Zhang [4] proved that the graph attaining
the maximum spectral radius among all $n$-vertex $S_{k}^{3}$-free graphs is a
member of $\mathrm{Ex}(n,S_{k}^{3})$. In 2022, Zhai, Liu and Xue [22]
determined the unique spectral extremal graphs for $S_{k}^{3}$ when $n$ is
sufficiently large. Let $H_{s,k}$ be the graph obtained from s triangles and
$k$ odd cycles of lengths at least $5$ by sharing a common vertex. Li and Peng
[7] showed that $\mathrm{Ex_{sp}}(n,H_{s,k})\subseteq\mathrm{Ex}(n,H_{s,k})$
for $n$ large enough. Lin, Zhai and Zhao [8] proved that
$\mathrm{Ex_{sp}}(n,\Gamma_{k})\subseteq\mathrm{Ex}(n,\Gamma_{k})$ for
sufficiently large $n$, where $\Gamma_{k}$ is the family of graphs consisting
of $k$-edge-disjoint triangles. Desai, Kang, Li, Ni, Tait and Wang [5]
generalized the result of [4] to $S_{k}^{p}$. Cioabă, Desai and Tait [3]
raised the following conjecture: Let $F$ be any graph such that the graphs in
$\mathrm{Ex}(n,F)$ are Turán graphs plus $O(1)$ edges. Then for sufficiently
large $n$, a graph attaining the maximum spectral radius among all $F$-free
graphs on $n$ vertices is a member of $\mathrm{Ex}(n,F)$. Wang, Kang and Xue
[20] proved the conjecture. Recently, Ni, Wang and Kang [12] proved that if
$G$ has the maximum spectral radius among all $M^{p+1}_{k}$-free graphs on $n$
vertices, then $G\in\mathrm{Ex}(n,M^{p+1}_{k})$.

In this paper, we consider the spectral extremal problem for the edge blow-up
of star forest $S^{p+1}_{k_{1},\cdots,k_{q}}$. The following result is
obtained.

######  Theorem 1.1.

Let $p\geq 2$, $q\geq 1$, and $k_{1}\geq k_{2}\geq\cdots\geq k_{q}\geq 1$. For
sufficiently large $n$, if $H$ has the maximum spectral radius among all
$n$-vertex $S^{p+1}_{k_{1},\cdots,k_{q}}$-free graphs, then

$H\in\mathrm{Ex}(n,S^{p+1}_{k_{1},\cdots,k_{q}}).$

##  2 Preliminaries

In this section, we give some notations and useful lemmas. Let $G$ be a simple
graph with matching number $\nu(G)$ and maximum degree $\Delta(G)$. For two
given integers $\nu$ and $\Delta$, define
$f(\nu,\Delta)=\max\\{e(G):\nu(G)\leq\nu,\Delta(G)\leq\Delta\\}$. In 1976,
Chvátal and Hanson [2] obtained the following result.

######  Theorem 2.1 ([2]).

For integers $\nu\geq 1$ and $\Delta\geq 1$, we have

$f(\nu,\Delta)=\Delta\nu+\left\lfloor\frac{\Delta}{2}\right\rfloor\left\lfloor\frac{\nu}{\lceil{\Delta}/{2}\rceil}\right\rfloor\leq\Delta\nu+\nu.$

Denote by $\mathcal{E}_{\nu,\Delta}$ the set of the graphs obtained the upper
bound in Theorem 2.1. Let $H(n,p,q)={K}_{q-1}\vee T_{p}(n-q+1)$ and
$\mathcal{H}(n,p,q,k_{q}-1)$ be a set of graphs obtained from $K_{q-1}\vee
T_{p}(n-q+1)$ by putting a copy of
${E}_{k_{q}-1,k_{q}-1}\in\mathcal{E}_{k_{q}-1,k_{q}-1}$ in one class of
$T_{p}(n-q+1)$. Let $h(n,p,q)=e(H(n,p,q))$. Using Theorem 2.3 in [21] on graph
$G=S_{k_{1},\cdots,k_{q}}$, we obtain that

$\mathrm{ex}(n,S^{p+1}_{k_{1},\cdots,k_{q}})\leq h(n,p,q)+f(k_{q}-1,k_{q}-1).$

Combining with the fact that the graphs in $\mathcal{H}(n,p,q,k_{q}-1)$ are
$S^{p+1}_{k_{1},\cdots,k_{q}}$-free, we have the following result.

######  Theorem 2.2.

If $n$ is large enough, then we have

$\mathrm{ex}(n,S^{p+1}_{k_{1},\cdots,k_{q}})=h(n,p,q)+f(k_{q}-1,k_{q}-1).$ (1)

Moreover, the graphs in $\mathcal{H}(n,p,q,k_{q}-1)$ are the only extremal
graph for $S^{p+1}_{k_{1},\cdots,k_{q}}$.

Chen, Gould, Pfender and Wei [1] gave the following lemma.

######  Lemma 2.1 ([1]).

Suppose that $G$ is a $S_{k}^{r}$-free graph, and $V(G)=V_{1}\cup
V_{2}\cup\cdots\cup V_{r-1}$ is a vertex partition of $G$. Let
$E_{cr}(G)=\cup_{1\leq i<j\leq r-1}E(V_{i},V_{j})$ be the set of crossing
edges of $G$. For any $i\in[r-1]$ and $v\in V_{i}$, if

$\displaystyle\sum_{j\neq i}\nu(G[V_{j}])\leq k-1\ \ \ \mbox{and}\ \ \
\Delta(G[V_{i}])\leq k-1,$ $\displaystyle d_{G[V_{i}]}(v)+\sum_{j\neq
i}\nu(G[N(v)\cap V_{j}])\leq k-1,$

then

$\sum_{i=1}^{r-1}|E(G[V_{i}])|-\left(\sum_{1\leq i<j\leq
r-1}|V_{i}||V_{j}|-|E_{cr}(G)|\right)\leq f(k-1,k-1).$

The following lemma was given in [4].

######  Lemma 2.2 ([4]).

Let $V_{1},\cdots,V_{n}$ be $n$ finite sets. Then

$|V_{1}\cap\cdots\cap
V_{n}|\geq\sum_{i=1}^{n}|V_{i}|-(n-1)|\bigcup_{i=1}^{n}V_{i}|$

By the Perron-Frobenius theorem, $\rho(G)$ is the largest eigenvalue of
$A(G)$. Let $\mathbf{x}=(x_{1},\cdots,x_{n})^{\mathrm{T}}$ be an eigenvector
corresponding to $\rho(G)$. Then for any $i\in[n]$ and $x_{i}\neq 0$,

$\rho(G)x_{i}=\sum_{ij\in E(G)}x_{j}.$ (2)

By the Rayleigh quotient, we have

$\rho(G)=\max_{\mathbf{x}\in\mathbb{R}^{n}_{+}}\frac{\mathbf{x}^{\mathrm{T}}A(G)\mathbf{x}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}=\max_{\mathbf{x}\in\mathbb{R}^{n}_{+}}\frac{2\sum_{ij\in
E(G)}x_{i}x_{j}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}.$ (3)

From the spectral version of the Stability Theorem given by Nikiforov [14], we
get the following result.

######  Lemma 2.3 ([5]).

Let $F$ be a graph with chromatic number $\chi(F)=r+1$. For every
$\varepsilon>0$, there exist $\delta>0$ and $n_{0}$ such that if $G$ is an
$F$-free graph on $n\geq n_{0}$ vertices with
$\rho(G)\geq(1-\frac{1}{r}-\delta)n$, then $G$ can be obtained from $T_{r}(n)$
by adding and deleting at most $\varepsilon n^{2}$ edges.

##  3 Proof of Theorem 1.1

In this section, we suppose that $H$ has the maximum spectral radius among all
$n$-vertex $S^{p+1}_{k_{1},\cdots,k_{q}}$-free graphs. Then we will prove that
$e(H)=\mathrm{ex}(n,S^{p+1}_{k_{1},\cdots,k_{q}})$ for sufficiently large $n$.
Clearly, $H$ is connected. Let $\rho(H)$ be the spectral radius of $H$. Then
by the Perron-Frobenius theorem, there exist positive eigenvectors
corresponding to $\rho(H)$. Let $\mathbf{x}$ be a positive eigenvector
corresponding to $\rho(H)$ with $\max\\{x_{i}:i\in V(H)\\}=1$. Without loss of
generality, we assume that $x_{z}=1$.

######  Lemma 3.1.

Let $H$ be an $n$-vertex $S^{p+1}_{k_{1},\cdots,k_{q}}$-free graph with
maximum spectral radius. Then

$\rho(H)\geq\frac{p-1}{p}n+O(1).$

Proof. Let $H^{\prime}$ be an $n$-vertex $S^{p+1}_{k_{1},\cdots,k_{q}}$-free
graph with $e(H^{\prime})=\mathrm{ex}(n,S^{p+1}_{k_{1},\cdots,k_{q}})$. By
(1), we have

$\displaystyle e(H^{\prime})$ $\displaystyle\geq
e(T_{p}(n-q+1))+(q-1)(n-q+1)+\binom{q-1}{2}$ $\displaystyle\geq
e(T_{p}(n))+\frac{q-1}{p}n-\frac{(q-1)(p+q-1)}{2p}-\frac{p}{8}.$

According to (3), for sufficiently $n$, we have

$\displaystyle\rho(H)$
$\displaystyle\geq\rho(H^{\prime})\geq\frac{\mathbf{1}^{\mathrm{T}}A(H^{\prime})\mathbf{1}}{\mathbf{1}^{\mathrm{T}}\mathbf{1}}=\frac{2e(H^{\prime})}{n}$
$\displaystyle\geq\frac{2}{n}\left(e(T_{p}(n))+\frac{q-1}{p}n-\frac{(q-1)(p+q-1)}{2p}-\frac{p}{8}\right)$
$\displaystyle\geq\frac{p-1}{p}n+\frac{2(q-1)}{p}-\frac{1}{n}\left(\frac{(q-1)(p+q-1)}{p}+\frac{p}{2}\right)$
$\displaystyle\geq\frac{p-1}{p}n+O(1).$

∎

By Lemmas 2.3, 3.1 and similar discussion as in [20], we have the following
lemmas.

######  Lemma 3.2.

Let $H$ be an $n$-vertex $S^{p+1}_{k_{1},\cdots,k_{q}}$-free graph with
maximum spectral radius. For every $\varepsilon>0$ and sufficiently large $n$,

$e(H)\geq e(T_{p}(n))-\varepsilon n^{2}.$

Furthermore, there exists $\varepsilon_{1}>0$ such that $H$ has a partition
$V(H)=V_{1}\cup\cdots\cup V_{p}$ with $\sum_{1\leq i<j\leq p}e(V_{i},V_{j})$
attaining the maximum,

$\sum_{i=1}^{p}e(V_{i})\leq\varepsilon n^{2},$

and for any $i\in[p]$

$\frac{n}{p}-\varepsilon_{1}n<|V_{i}|<\frac{n}{p}+\varepsilon_{1}n.$

######  Lemma 3.3.

Suppose that $\varepsilon$ and $\theta$ are two sufficiently small constants
with $\varepsilon\leq\theta^{2}$. Let

$W:=\cup_{i=1}^{p}\\{v\in V_{i}:d_{V_{i}}(v)\geq 2\theta n\\}.$

Then $|W|\leq\theta n$.

######  Lemma 3.4.

Suppose that $\varepsilon_{2}$ is a sufficiently small constant with
$\varepsilon<\varepsilon_{2}\ll\theta$. Let

$L:=\\{v\in V(H):d(v)\leq(1-\frac{1}{p}-\varepsilon_{2})n\\}.$

Then $|L|\leq\varepsilon_{3}n$, where $\varepsilon_{3}\ll\varepsilon_{2}$ is a
sufficiently small constant satisfying
$\varepsilon-\varepsilon_{2}\varepsilon_{3}+\frac{p-1}{2p}\varepsilon_{3}^{2}<0$.

Proof. Suppose to the contrary that $|L|>\varepsilon_{3}n$, then there exists
$L^{\prime}\subseteq L$ with $|L^{\prime}|=\lfloor\varepsilon_{3}n\rfloor$.
Therefore,

$\displaystyle e(H\setminus L^{\prime})$ $\displaystyle\geq$ $\displaystyle
e(H)-\sum_{v\in L^{\prime}}d(v)$ $\displaystyle\geq$ $\displaystyle
e(T_{p}(n))-\varepsilon
n^{2}-\lfloor\varepsilon_{3}n\rfloor(1-\frac{1}{p}-\varepsilon_{2})n$
$\displaystyle>$
$\displaystyle\frac{p-1}{2p}(n-\lfloor\varepsilon_{3}n\rfloor-q+1)^{2}+(q-1)(n-\lfloor\varepsilon_{3}n\rfloor-q+1)+\binom{q-1}{2}+k_{q}^{2}$
$\displaystyle\geq$ $\displaystyle e({K}_{q-1}\vee
T_{p}(n-\lfloor\varepsilon_{3}n\rfloor-q+1))+f(k_{q}-1,k_{q}-1)$
$\displaystyle=$
$\displaystyle\mathrm{ex}(n-\lfloor\varepsilon_{3}n\rfloor,S^{p+1}_{k_{1},\cdots,k_{q}}).$

Since $e(H\setminus
L^{\prime})>\mathrm{ex}(n-|L^{\prime}|,S^{p+1}_{k_{1},\cdots,k_{q}})$,
$H\setminus L^{\prime}$ contains a copy of $S^{p+1}_{k_{1},\cdots,k_{q}}$.
This contradicts the fact that $H$ is $S^{p+1}_{k_{1},\cdots,k_{q}}$-free. ∎

######  Lemma 3.5.

For an arbitrary subset $S\subseteq V_{i}\setminus(W\cup L)$, $i\in[p]$, there
exists a subgraph $H^{\prime}$ in $H$ such that $H^{\prime}$ is a copy of
$T_{p}(p|S|)$ and $V(H^{\prime})\cap V_{i}=S$.

Proof. For any $i\in[p]$ and any vertex $w\in V_{i}\setminus(W\cup L)$, we
have $d(w)>(1-\frac{1}{p}-\varepsilon_{2})n$ and $d_{V_{i}}(w)<2\theta n$.
Then for any $j\in[p]$ and $j\neq i$, we have

$\displaystyle d_{V_{j}}(w)$ $\displaystyle\geq$ $\displaystyle
d(w)-d_{V_{i}}(w)-(p-2)(\frac{n}{p}+\varepsilon_{1}n)$ $\displaystyle>$
$\displaystyle(1-\frac{1}{p}-\varepsilon_{2})n-2\theta
n-(p-2)(\frac{n}{p}+\varepsilon_{1}n)$ $\displaystyle>$
$\displaystyle\frac{n}{p}-3\theta n-(p-2)\varepsilon_{1}n.$

Take an arbitrary subset $S\subseteq V_{i}\setminus(W\cup L)$. Without loss of
generality, let $i=1$ and $S=\\{u_{1,1},\cdots,u_{1,t}\\}$. We consider the
common neighbors of $\\{u_{1,1},\cdots,u_{1,t}\\}$ in $V_{2}\setminus(W\cup
L)$. Combining with Lemma 2.2, we have

$\displaystyle|(\cap_{j\in[t]}N_{V_{2}}(u_{1,j}))\setminus(W\cup L)|$
$\displaystyle\geq$
$\displaystyle\sum_{j=1}^{t}d_{V_{2}}(u_{1,j})-(t-1)|V_{2}|-|W|-|L|$
$\displaystyle>$ $\displaystyle t(\frac{n}{p}-3\theta
n-(p-2)\varepsilon_{1}n)-(t-1)(\frac{n}{p}+\varepsilon_{1}n)-\theta
n-\varepsilon_{3}n$ $\displaystyle>$ $\displaystyle\frac{n}{p}-o(n)$
$\displaystyle>$ $\displaystyle t.$

So there exist vertices $u_{2,1},\cdots,u_{2,t}\in V_{2}\setminus(W\cup L)$
such that $\\{u_{1,1},\cdots,u_{1,t}\\}\cup\\{u_{2,1},\cdots,u_{2,t}\\}$ can
induce a complete bipartite subgraph in $H$. For an integer $s$ with $2\leq
s\leq p-1$, suppose that there are vertices $u_{s,1},\cdots,u_{s,t}\in
V_{s}\setminus(W\cup L)$ such that $\\{u_{1,1},\cdots,u_{1,t}\\}~{}\cup$
$\\{u_{2,1},\cdots,u_{2,t}\\}~{}\cup$ $\cdots~{}\cup$
$\\{u_{s,1},\cdots,u_{s,t}\\}$ induce a complete $s$-partite subgraph in $H$.
We next consider the common neighbors of the above $st$ vertices in
$V_{s+1}\setminus(W\cup L)$. By Lemma 2.2, we have

$\displaystyle|(\cap_{i\in[s],j\in[t]}N_{V_{s+1}}(u_{i,j}))\setminus(W\cup
L)|$ $\displaystyle\geq$
$\displaystyle\sum_{i=1}^{s}\sum_{j=1}^{t}d_{V_{s+1}}(u_{i,j})-(st-1)|V_{s+1}|-|W|-|L|$
$\displaystyle>$ $\displaystyle st(\frac{n}{p}-3\theta
n-(p-2)\varepsilon_{1}n)-(st-1)(\frac{n}{p}+\varepsilon_{1}n)-\theta
n-\varepsilon_{3}n$ $\displaystyle>$ $\displaystyle\frac{n}{p}-o(n)$
$\displaystyle>$ $\displaystyle t.$

Then we can find vertices $u_{s+1,1},\cdots,u_{s+1,t}$ $\in
V_{s+1}\setminus(W\cup L)$ such that $\\{u_{1,1},\cdots,u_{1,t}\\}~{}\cup$
$\\{u_{2,1},\cdots,u_{2,t}\\}~{}\cup$ $\cdots~{}\cup$
$\\{u_{s+1,1},\cdots,u_{s+1,t}\\}$ induce a complete $(s+1)$-partite subgraph
in $H$. Therefore, for every $2\leq i\leq p$, there exist vertices
$u_{p,1},\cdots,u_{p,t}$ $\in V_{i}\setminus(W\cup L)$ such that
$\\{u_{1,1},\cdots,u_{1,t}\\}~{}\cup$ $\\{u_{2,1},\cdots,u_{2,t}\\}~{}\cup$
$\cdots~{}\cup$ $\\{u_{p,1},\cdots,u_{p,t}\\}$ induce a complete $p$-partite
subgraph $H^{\prime}$ in $H$. The result follows. ∎

######  Lemma 3.6.

For each $i\in[p]$,

$\Delta(H[V_{i}\setminus(W\cup L)])<q(k_{1}p+1),$ $\nu(H[V_{i}\setminus(W\cup
L)])<\sum_{i\in[q]}k_{i},$

and there exists an independent set $I_{i}\subseteq V_{i}\setminus(W\cup L)$
such that

$|I_{i}|\geq|V_{i}\setminus(W\cup L)|-2(\sum_{i\in[q]}k_{i}-1).$

Proof. We first prove that $\Delta(H[V_{i}\setminus(W\cup L)])<q(k_{1}p+1)$
for any $i\in[p]$. Suppose to contrary that there exist $i_{0}\in[p]$ and
$u\in V_{i_{0}}\setminus(W\cup L)$ such that $d_{V_{i_{0}}\setminus(W\cup
L)}(u)\geq q(k_{1}p+1)$. As $u\in V_{i_{0}}\setminus(W\cup L)$, there exists a
vertex $w$ such that $uw\notin E(H)$. Let $H^{\prime}$ be the graph with
$V(H^{\prime})=V(H)$ and $E(H^{\prime})=E(H)\cup\\{uw\\}$. Then $H$ is a
proper subgraph of $H^{\prime}$. By the maximum of $\rho(H)$, $H^{\prime}$
contains a copy of $S^{p+1}_{k_{1},\cdots,k_{q}}$, say $H_{1}$. From the
construction of $H^{\prime}$, we see that $u\in V(H_{1})$, and there is an
$j_{0}\in[q]$ such that $H_{1}\setminus\\{u\\}$ contains a copy of
$\cup_{i\in[q]\setminus\\{j_{0}\\}}S^{p+1}_{k_{i}}$, say $H_{2}$. Obviously,
$H_{2}\subseteq H$. Let $S=N_{V_{i_{0}}\setminus(W\cup L)}(u)$. Since
$d_{V_{i_{0}}\setminus(W\cup L)}(u)\geq q(k_{1}p+1)$, by Lemma 3.5 there
exists a copy of $S^{p+1}_{k_{j_{0}}}$ with center $u$, denoted by $H_{3}$,
such that $V(H_{3})\cap V(H_{2})=\emptyset$. Thus $H_{2}\cup H_{3}$ is a copy
of $S^{p+1}_{k_{1},\cdots,k_{q}}$ in $H$, which contradicts the fact that $H$
is $S^{p+1}_{k_{1},\cdots,k_{q}}$-free.

Now we claim that for any $i\in[p]$, $\nu(H[V_{i}\setminus(W\cup
L)])<\sum_{i\in[q]}k_{i}$. Otherwise, there exists $i_{0}\in[p]$ such that
$H[V_{i_{0}}\setminus(W\cup L)]$ contains a matching $M$ with
$\sum_{i\in[q]}k_{i}$ edges. By Lemma 3.5, there is a copy of $T_{p}(2|M|p)$
with $V(T_{p}(2|M|p))\cap V_{i_{0}}=V(M)$. Since
$|V(M)|=2|M|=2\sum_{i\in[q]}k_{i}$, we can find a copy of
$S^{p+1}_{k_{1},\cdots,k_{q}}$ in $H$, a contradiction.

For every $i\in[p]$, let $M^{i}$ be a maximum matching of
$H[V_{i}\setminus(W\cup L)]$, and $C^{i}$ be the set of vertices covered by
$M^{i}$. Then $|C^{i}|\leq 2(\sum_{i\in[q]}k_{i}-1)$. By deleting all vertices
of $C^{i}$, we can find an independent set $I_{i}\subseteq
V_{i}\setminus(W\cup L)$. Therefore, $|I_{i}|\geq|V_{i}\setminus(W\cup
L)|-2(\sum_{i\in[q]}k_{i}-1)$. ∎

######  Lemma 3.7.

$|W\setminus L|\leq q-1$, and for any $u\in W\setminus L$, $d(u)=n-1$.

Proof. We first prove the following claim.

Claim A.  For any $u\in W\setminus L$, $H$ contains a copy of
$S^{p+1}_{q(k_{1}p+1)}$ with center $u$.

For any $u\in W\setminus L$, we have $d(u)>(1-\frac{1}{p}-\varepsilon_{2})n$.
Without loss of generality, we may assume that $u\in V_{1}$. Since
$V(H)=V_{1}\cup\cdots\cup V_{p}$ is the vertex partition that maximizes the
number of crossing edges of $H$, $d_{V_{1}}(u)\leq\frac{1}{p}d(u)$. For any
$2\leq j\leq p$,

$\displaystyle d_{V_{j}}(u)$ $\displaystyle\geq$ $\displaystyle
d(u)-d_{V_{1}}(u)-(p-2)(\frac{n}{p}+\varepsilon_{1}n)$ (4) $\displaystyle>$
$\displaystyle\frac{p-1}{p}(1-\frac{1}{p}-\varepsilon_{2})n-(p-2)(\frac{n}{p}+\varepsilon_{1}n)$
$\displaystyle>$ $\displaystyle\frac{n}{p^{2}}-\theta
n-(p-2)\varepsilon_{1}n.$

For any $i\in[p]$ and $v\in V_{i}\setminus(W\cup L)$, we have
$d(v)>(1-\frac{1}{p}-\varepsilon_{2})n$ and $d_{V_{i}}(v)<2\theta n$. Then for
any $j\in[p]$ and $j\neq i$, we have

$\displaystyle d_{V_{j}}(v)$ $\displaystyle\geq$ $\displaystyle
d(v)-d_{V_{i}}(v)-(p-2)(\frac{n}{p}+\varepsilon_{1}n)$ (5) $\displaystyle>$
$\displaystyle\frac{n}{p}-\varepsilon_{2}n-2\theta n-(p-2)\varepsilon_{1}n$
$\displaystyle>$ $\displaystyle\frac{n}{p}-3\theta n-(p-2)\varepsilon_{1}n.$

By Lemmas 3.3 and 3.4, we have

$\displaystyle d_{V_{1}\setminus(W\cup L)}(u)$ $\displaystyle\geq$
$\displaystyle d_{V_{1}}(u)-|W\cup L|$ $\displaystyle\geq$ $\displaystyle
2\theta n-\theta n-\varepsilon_{2}n$ $\displaystyle>$ $\displaystyle
q(k_{1}p+1).$

Let $u_{1,1},\cdots,u_{1,q(k_{1}p+1)}$ be the neighbors of $u$ in
$V_{1}\setminus(W\cup L)$. We consider the common neighbors of
$u,u_{1,1},\cdots,u_{1,q(k_{1}p+1)}$ in $V_{2}\setminus(W\cup L)$. Combining
with (4), (5) and Lemma 2.2, we have

$\displaystyle|N_{V_{2}}(u)\cap(\cap_{i\in[q(k_{1}p+1)]}N_{V_{2}}(u_{1,i}))\setminus(W\cup
L)|$ $\displaystyle\geq$ $\displaystyle
d_{V_{2}}(u)+\sum_{i=1}^{q(k_{1}p+1)}d_{V_{2}}(u_{1,i})-q(k_{1}p+1)|V_{2}|-|W|-|L|$
$\displaystyle>$ $\displaystyle\frac{n}{p^{2}}-\theta
n-(p-2)\varepsilon_{1}n+q(k_{1}p+1)(\frac{n}{p}-3\theta
n-(p-2)\varepsilon_{1}n)-q(k_{1}p+1)(\frac{n}{p}+\varepsilon_{1}n)-\theta
n-\varepsilon_{3}n$ $\displaystyle>$ $\displaystyle\frac{n}{p^{2}}-o(n)$
$\displaystyle>$ $\displaystyle q(k_{1}p+1).$

Let $u_{2,1},\cdots,u_{2,q(k_{1}p+1)}$ be the common neighbors of
$\\{u,u_{1,1},\cdots,u_{1,q(k_{1}p+1)}\\}$ in $V_{2}\setminus(W\cup L)$. For
an integer $2\leq s\leq p-1$, suppose that $u_{s,1},\cdots,u_{s,q(k_{1}p+1)}$
are the common neighbors of $\\{u,u_{i,1},\cdots,u_{i,q(k_{1}p+1)}:1\leq i\leq
s-1\\}$ in $V_{s}\setminus(W\cup L)$. We next consider the common neighbors of
$\\{u,u_{i,1},\cdots,u_{i,q(k_{1}p+1)}:1\leq i\leq s\\}$ in
$V_{s+1}\setminus(W\cup L)$. By (4), (5) and Lemma 2.2, we have

$\displaystyle|N_{V_{s+1}}(u)\cap(\cap_{i\in[s],j\in[q(k_{1}p+1)]}N_{V_{s+1}}(u_{i,j}))\setminus(W\cup
L)|$ $\displaystyle\geq$ $\displaystyle
d_{V_{s+1}}(u)+\sum_{i=1}^{s}\sum_{j=1}^{q(k_{1}p+1)}d_{V_{s+1}}(u_{i,j})-sq(k_{1}p+1)|V_{s+1}|-|W|-|L|$
$\displaystyle>$ $\displaystyle\frac{n}{p^{2}}-\theta
n-(p-2)\varepsilon_{1}n+sq(k_{1}p+1)(\frac{n}{p}-3\theta
n-(p-2)\varepsilon_{1}n)-sq(k_{1}p+1)(\frac{n}{p}+\varepsilon_{1}n)-\theta
n-\varepsilon_{3}n$ $\displaystyle>$ $\displaystyle\frac{n}{p^{2}}-o(n)$
$\displaystyle>$ $\displaystyle q(k_{1}p+1).$

Let $u_{s+1,1},\cdots,u_{s+1,q(k_{1}p+1)}$ be the common neighbors of
$\\{u,u_{i,1},\cdots,u_{i,q(k_{1}p+1)}:1\leq i\leq s\\}$ in
$V_{s+1}\setminus(W\cup L)$. Therefore, for every $i\in[p]$, there exist
$u_{i,1},\cdots,u_{i,q(k_{1}p+1)}\in V_{i}\setminus(W\cup L)$ such that
$\\{u_{1,1},\cdots,u_{1,q(k_{1}p+1)}\\}$
$\cup~{}\\{u_{2,1},\cdots,u_{2,q(k_{1}p+1)}\\}$ $\cup~{}\cdots~{}\cup$
$\\{u_{p,1},\cdots,u_{p,q(k_{1}p+1)}\\}$ form a complete $p$-partite subgraph
of $H$, and $u$ is adjacent to all the above $pq(k_{1}p+1)$ vertices. Hence we
can find a copy of $S^{p+1}_{q(k_{1}p+1)}$ with center $u$.

Now we prove that $|W\setminus L|\leq q-1$. Suppose to the contrary that
$|W\setminus L|\geq q$. By Claim A, for any $u\in W\setminus L$, we can find a
copy of $S^{p+1}_{q(k_{1}p+1)}$ with center $u$ in $H$. Therefore, we can find
$q$ disjoint copies of $S^{p+1}_{k_{1}}$ in $H$. This contradicts the fact
that $H$ is $S^{p+1}_{k_{1},\cdots,k_{q}}$-free.

Next we prove that for any $u\in W\setminus L$, $d(u)=n-1$. Suppose to the
contrary that there exists $u\in W\setminus L$ such that $d(u)<n-1$. Assume
that $v$ is a vertex of $H$ such that $uv\notin E(H)$. Let $H^{\prime}$ be the
graph with $V(H^{\prime})=V(H)$ and $E(H^{\prime})=E(H)\cup\\{uv\\}$. We claim
that $H^{\prime}$ is $S^{p+1}_{k_{1},\cdots,k_{q}}$-free. Otherwise,
$H^{\prime}$ contains a copy of $S^{p+1}_{k_{1},\cdots,k_{q}}$, say $H_{1}$,
then $uv\in E(H_{1})$. Therefore, $H_{1}$ contains a copy of
$S^{p+1}_{k_{i_{0}}}$, say $H_{2}$, such that $uv\in E(H_{2})$, where
$i_{0}\in[q]$. Let $H_{3}=H_{1}\setminus H_{2}$. Then $H_{3}$ is a copy of
$\cup_{i\in[q]\setminus\\{i_{0}\\}}S^{p+1}_{k_{i}}$ in $H$. Since $u\in
W\setminus L$, we can find a copy of $S^{p+1}_{q(k_{1}p+1)}$ with center $u$
in $H$ by Claim A. Thus there is a copy of $S^{p+1}_{k_{i_{0}}}$ with center
$u$ in $H$, denoted by $H_{4}$, such that $V(H_{4})\cap V(H_{3})=\emptyset$.
Then $H_{3}\cup H_{4}$ is a copy of $S^{p+1}_{k_{1},\cdots,k_{q}}$ in $H$, and
this is a contradiction. Therefore, $H^{\prime}$ is
$S^{p+1}_{k_{1},\cdots,k_{q}}$-free. By the construction of $H^{\prime}$, we
have $\rho(H^{\prime})>\rho(H)$, which contradicts the assumption that $H$ has
the maximum spectral radius among all $n$-vertex
$S^{p+1}_{k_{1},\cdots,k_{q}}$-free graphs. ∎

######  Lemma 3.8.

Let $x_{v_{0}}=\max\\{x_{v}:v\in V(H)\setminus W\\}$. Then
$x_{v_{0}}>1-\frac{2}{p}$ and $v_{0}\notin L$.

Proof. Recall that $x_{z}=\max\\{x_{v}:v\in V(H)\\}=1$, then

$\rho(H)=\rho(H)x_{z}\leq|W|+(n-|W|)x_{v_{0}}.$

By Lemmas 3.4 and 3.7, we have

$\displaystyle|W|=|W\cap L|+|W\setminus
L|\leq|L|+q-1\leq\varepsilon_{3}n+q-1.$ (6)

Combining with Lemma 3.1, we have

$\displaystyle
x_{v_{0}}\geq\frac{\rho(H)-|W|}{n-|W|}\geq\frac{\rho(H)-|W|}{n}\geq
1-\frac{1}{p}-\varepsilon_{3}-\frac{O(1)}{n}>1-\frac{2}{p}.$ (7)

Therefore, we have

$\displaystyle\rho(H)x_{v_{0}}$ $\displaystyle=$ $\displaystyle\sum_{v\sim
v_{0}}x_{v}=\sum_{\begin{subarray}{c}v\in W,\\\ v\sim
v_{0}\end{subarray}}x_{v}+\sum_{\begin{subarray}{c}v\notin W,\\\ v\sim
v_{0}\end{subarray}}x_{v}$ (8) $\displaystyle\leq$
$\displaystyle|W|+(d(v_{0})-|W|)x_{v_{0}}.$

By (6), (7), (8) and Lemma 3.1, we have

$\displaystyle d(v_{0})$ $\displaystyle\geq$
$\displaystyle\rho(H)+|W|-\frac{|W|}{x_{v_{0}}}$ $\displaystyle\geq$
$\displaystyle\rho(H)-\frac{2|W|}{p-2}$ $\displaystyle\geq$
$\displaystyle\frac{p-1}{p}n+O(1)-\frac{2\varepsilon_{3}n}{p-2}-\frac{2(q-1)}{p-2}$
$\displaystyle>$ $\displaystyle(1-\frac{1}{p}-\varepsilon_{2})n,$

where the last inequality holds as $\varepsilon_{3}\ll\varepsilon_{2}$. Thus
$v_{0}\notin L$. ∎

######  Lemma 3.9.

$L=\emptyset.$

Proof. Suppose to the contrary that there is a vertex $u_{0}\in L$, then
$d(u_{0})\leq(1-\frac{1}{p}-\varepsilon_{2})n$. Let $H^{\prime}$ be the graph
with $V(H^{\prime})=V(H)$ and
$E(H^{\prime})=E(H\setminus\\{u_{0}\\})\cup\\{wu_{0}:w\in\cup_{i=2}^{p}I_{i}\\}$.
It is obvious that $H^{\prime}$ is $S^{p+1}_{k_{1},\cdots,k_{q}}$-free. By
Lemma 3.8, $v_{0}\in V(H)\setminus(W\cup L)$. Without loss of generality, we
assume that $v_{0}\in V_{1}\setminus(W\cup L)$. Combining with Lemma 3.6, we
have

$\displaystyle\rho(H)x_{v_{0}}$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}v\in W\cup L,\\\ v\sim
v_{0}\end{subarray}}x_{v}+\sum_{\begin{subarray}{c}v\in V_{1}\setminus(W\cup
L),\\\ v\sim
v_{0}\end{subarray}}x_{v}+\sum_{\begin{subarray}{c}v\in(\cup_{i=2}^{p}V_{i})\setminus(W\cup
L),\\\ v\sim v_{0}\end{subarray}}x_{v}$ $\displaystyle<$
$\displaystyle|W|+|L|x_{v_{0}}+q(k_{1}p+1)x_{v_{0}}+\sum_{\begin{subarray}{c}v\in(\cup_{i=2}^{p}V_{i}\setminus
I_{i})\setminus(W\cup L),\\\ v\sim
v_{0}\end{subarray}}x_{v}+\sum_{\begin{subarray}{c}v\in\cup_{i=2}^{p}I_{i},\\\
v\sim v_{0}\end{subarray}}x_{v}$ $\displaystyle\leq$
$\displaystyle|W|+|L|x_{v_{0}}+q(k_{1}p+1)x_{v_{0}}+2(\sum_{i\in[q]}k_{i}-1)(p-1)x_{v_{0}}+\sum_{\begin{subarray}{c}v\in\cup_{i=2}^{p}I_{i}\end{subarray}}x_{v},$

which implies that

$\sum_{\begin{subarray}{c}v\in\cup_{i=2}^{p}I_{i}\end{subarray}}x_{v}\geq(\rho(H)-|L|-q(k_{1}p+1)-2(\sum_{i\in[q]}k_{i}-1)(p-1))x_{v_{0}}-|W|.$

Combining with Lemmas 3.1, 3.4 and 3.8, we have

$\displaystyle\rho(H^{\prime})-\rho(H)$ $\displaystyle\geq$
$\displaystyle\frac{\mathbf{x}^{T}\left(A(H^{\prime})-A(H)\right)\mathbf{x}}{\mathbf{x}^{T}\mathbf{x}}$
$\displaystyle=$
$\displaystyle\frac{2x_{u_{0}}}{\mathbf{x}^{T}\mathbf{x}}\left(\sum_{\begin{subarray}{c}w\in\cup_{i=2}^{p}I_{i}\end{subarray}}x_{w}-\sum_{u\sim
u_{0}}x_{u}\right)$ $\displaystyle\geq$
$\displaystyle\frac{2x_{u_{0}}}{\mathbf{x}^{T}\mathbf{x}}\Bigl{(}(\rho(H)-|L|-q(k_{1}p+1)-2(\sum_{i\in[q]}k_{i}-1)(p-1))x_{v_{0}}-2|W|-(d(u_{0})-|W|)x_{v_{0}}\Bigr{)}$
$\displaystyle=$
$\displaystyle\frac{2x_{u_{0}}}{\mathbf{x}^{T}\mathbf{x}}\Bigl{(}(\rho(H)-|L|-q(k_{1}p+1)-2(\sum_{i\in[q]}k_{i}-1)(p-1)-d(u_{0})+|W|)x_{v_{0}}-2|W|\Bigr{)}$
$\displaystyle\geq$
$\displaystyle\frac{2x_{u_{0}}}{\mathbf{x}^{T}\mathbf{x}}\Bigl{(}\frac{p-2}{p}(\varepsilon_{2}n-\varepsilon_{3}n-O(1))-2(\varepsilon_{3}n+q-1)\Bigr{)}>0,$

where the last inequality holds since $\varepsilon_{3}\ll\varepsilon_{2}$.
This contradicts the fact that $H$ has the largest spectral radius over all
$n$-vertex $S^{p+1}_{k_{1},\cdots,k_{q}}$-free graphs. So $L$ must be empty. ∎

######  Lemma 3.10.

For any $v\in V(H)$, $x_{v}\geq x_{v_{0}}-\frac{100k_{1}pq}{n}$.

Proof. Suppose to the contrary that there exists $u\in V(H)$ such that
$x_{u}<x_{v_{0}}-\frac{100k_{1}pq}{n}$. Let $H^{\prime}$ be the graph with
$V(H^{\prime})=V(H)$ and
$E(H^{\prime})=E(H\setminus\\{u\\})\cup\\{uw:w\in\cup_{i=2}^{p}I_{i}\\}$. It
is obvious that $H^{\prime}$ is $S^{p+1}_{k_{1},\cdots,k_{q}}$-free. Since
$L=\emptyset$, then $|W|=|W\setminus L|\leq q-1$ by Lemma 3.7. Recall that
$x_{v_{0}}=\max\\{x_{v}:v\in V(H)\setminus W\\}$, then

$\displaystyle\rho(H)x_{v_{0}}$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}v\in W,\\\ v\sim
v_{0}\end{subarray}}x_{v}+\sum_{\begin{subarray}{c}v\in V_{1}\setminus W,\\\
v\sim
v_{0}\end{subarray}}x_{v}+\sum_{\begin{subarray}{c}v\in(\cup_{i=2}^{p}V_{i})\setminus
W,\\\ v\sim v_{0}\end{subarray}}x_{v}$ $\displaystyle<$
$\displaystyle|W|+q(k_{1}p+1)x_{v_{0}}+\sum_{\begin{subarray}{c}v\in(\cup_{i=2}^{p}V_{i}\setminus
I_{i})\setminus W,\\\ v\sim
v_{0}\end{subarray}}x_{v}+\sum_{\begin{subarray}{c}v\in\cup_{i=2}^{p}I_{i},\\\
v\sim v_{0}\end{subarray}}x_{v}$ $\displaystyle\leq$ $\displaystyle
q-1+q(k_{1}p+1)x_{v_{0}}+2(\sum_{i\in[q]}k_{i}-1)(p-1)x_{v_{0}}+\sum_{\begin{subarray}{c}v\in\cup_{i=2}^{p}I_{i}\end{subarray}}x_{v},$

which implies that

$\sum_{\begin{subarray}{c}v\in\cup_{i=2}^{p}I_{i}\end{subarray}}x_{v}\geq(\rho(H)-q(k_{1}p+1)-2(\sum_{i\in[q]}k_{i}-1)(p-1))x_{v_{0}}-(q-1).$

Therefore, we have

$\displaystyle\rho(H^{\prime})-\rho(H)$ $\displaystyle\geq$
$\displaystyle\frac{2x_{u}}{\mathbf{x}^{T}\mathbf{x}}\Bigl{(}(\rho(H)-q(k_{1}p+1)-2(\sum_{i\in[q]}k_{i}-1)(p-1))x_{v_{0}}-(q-1)-\rho(H)x_{u}\Bigr{)}$
$\displaystyle>$
$\displaystyle\frac{2x_{u}}{\mathbf{x}^{T}\mathbf{x}}\Bigl{(}(\rho(H)-q(k_{1}p+1)-2(\sum_{i\in[q]}k_{i}-1)(p-1))x_{v_{0}}-(q-1)-\rho(H)(x_{v_{0}}-\frac{100k_{1}pq}{n})\Bigr{)}$
$\displaystyle>$
$\displaystyle\frac{2x_{u}}{\mathbf{x}^{T}\mathbf{x}}\Bigl{(}\frac{(p-1)n}{p}\frac{100k_{1}pq}{n}-q(k_{1}p+1)-2(\sum_{i\in[q]}k_{i}-1)(p-1)-(q-1)\Bigr{)}>0.$

This contradicts the fact that $H$ has the largest spectral radius over all
$n$-vertex $S^{p+1}_{k_{1},\cdots,k_{q}}$-free graphs. ∎

######  Lemma 3.11.

$|W|=q-1$.

Proof. Let $|W|=s$. Then $s\leq q-1$ by Lemmas 3.7 and 3.9. Suppose to the
contrary that $s<q-1$. By Lemmas 3.6 and 3.9, for any $i\in[p]$,
$\nu(H[V_{i}\setminus W])<\sum_{i\in[q]}k_{i}$ and $\Delta(H[V_{i}\setminus
W])<q(k_{1}p+1)$. Thus $\nu(\cup_{i=1}^{p}H[V_{i}\setminus
W])<p\sum_{i\in[q]}k_{i}$ and $\Delta(\cup_{i=1}^{p}H[V_{i}\setminus
W])<q(k_{1}p+1)$. Combining with Lemma 2.1, we have

$\displaystyle e(\cup_{i=1}^{p}H[V_{i}\setminus W])$ $\displaystyle\leq
f(\nu(\cup_{i=1}^{p}H[V_{i}\setminus W]),\Delta(\cup_{i=1}^{p}H[V_{i}\setminus
W]))$ $\displaystyle<f(p\sum_{i\in[q]}k_{i},q(k_{1}p+1))$
$\displaystyle<q(k_{1}p+1)(k_{1}pq+1).$

Take $S\subseteq V_{1}\setminus W$ with $|S|=q-s-1$. Let $H^{\prime}$ be the
graph with $V(H^{\prime})=V(H)$ and
$E(H^{\prime})=E(H)\setminus\\{uv:uv\in\cup_{i=1}^{p}E(H[V_{i}\setminus
W])\\}\cup\\{uv:u\in S,v\in(V_{1}\setminus W)\setminus S\\}$. It is obvious
that $H^{\prime}$ is $S^{p+1}_{k_{1},\cdots,k_{q}}$-free. Therefore,

$\displaystyle\rho(H^{\prime})-\rho(H)$
$\displaystyle\geq\frac{\mathbf{x}^{T}\left(A(H^{\prime})-A(H)\right)\mathbf{x}}{\mathbf{x}^{T}\mathbf{x}}$
$\displaystyle=\frac{2}{\mathbf{x}^{T}\mathbf{x}}\left(\sum_{ij\in
E(H^{\prime})}x_{i}x_{j}-\sum_{ij\in E(H)}x_{i}x_{j}\right)$
$\displaystyle\geq\frac{2}{\mathbf{x}^{T}\mathbf{x}}\left(|S|(|V_{1}|-|W|-|S|)(x_{v_{0}}-\frac{100k_{1}pq}{n})^{2}-q(k_{1}p+1)(k_{1}pq+1)\right)$
$\displaystyle\geq\frac{2}{\mathbf{x}^{T}\mathbf{x}}\Bigl{(}(q-s-1)(\frac{n}{p}-o(n))(\frac{p-2}{p}-o(1))^{2}-q(k_{1}p+1)(k_{1}pq+1)\Bigr{)}$
$\displaystyle>0.$

This contradicts the fact that $H$ has the largest spectral radius over all
$n$-vertex $S^{p+1}_{k_{1},\cdots,k_{q}}$-free graphs. Therefore, $|W|=s=q-1$.
∎

######  Lemma 3.12.

For any $i\in[p]$, let $B_{i}=\\{u\in V_{i}\setminus W:d_{V_{i}\setminus
W}(u)\geq 1\\}$ and $C_{i}=(V_{i}\setminus W)\setminus B_{i}$. Then
$|B_{i}|<2k_{q}^{2}$, and $u$ is adjacent to all vertices of $V(H)\setminus
V_{i}$ for every vertex $u\in C_{i}$.

Proof. We first prove the following claim.

Claim B. For any $i\in[p]$, $H[V_{i}\setminus W]$ is both $S_{k_{q}}$-free and
$M_{k_{q}}$-free.

Suppose to the contrary that there is an $i_{0}\in[p]$ such that
$H[V_{i_{0}}\setminus W]$ contains a $S_{k_{q}}$ or an $M_{k_{q}}$ as a
subgraph. Then $H$ contains a copy of $S^{p+1}_{k_{q}}$, say $H_{0}$, by
Lemmas 3.5 and 3.9. Since $|W|=q-1$ and each vertex of $W$ has degree $n-1$,
$H$ contains a copy of $S^{p+1}_{k_{1},\cdots,k_{q-1}}$, say $H_{0}^{\prime}$,
such that $V(H_{0})\cap V(H_{0}^{\prime})=\emptyset$. Thus $H_{0}\cup
H_{0}^{\prime}$ is a copy of $S^{p+1}_{k_{1},\cdots,k_{q}}$ in $H$, a
contradiction.

By Claim B, we have $e(H[V_{i}\setminus W])\leq f(k_{q}-1,k_{q}-1)<k_{q}^{2}$.
Therefore,

$|B_{i}|\leq\sum_{u\in B_{i}}d_{V_{i}}(u)=\sum_{u\in V_{i}\setminus
W}d_{V_{i}}(u)=2e(H[V_{i}\setminus W])<2k_{q}^{2}.$

Now we prove that each vertex of $C_{i}$ is adjacent to all vertices of
$V\setminus V_{i}$ for any $i\in[p]$. Since each vertex of $W$ has degree
$n-1$, we only need to prove that each vertex of $C_{i}$ is adjacent to all
vertices of $(V(H)\setminus W)\setminus V_{i}$ for any $i\in[p]$. Suppose to
the contrary that there exist $i_{0}\in[p]$ and $v\in C_{i_{0}}$ such that
there is a vertex $w_{1,1}\notin V_{i_{0}}\cup W$ and $vw_{1,1}\notin E(H)$.
Without loss of generality, we may assume that $i_{0}=1$. Let $H^{\prime}$ be
the graph with $V(H^{\prime})=V(H)$ and
$E(H^{\prime})=E(H)\cup\\{vw_{1,1}\\}$. We claim that $H^{\prime}$ is
$S^{p+1}_{k_{1},\cdots,k_{q}}$-free. Otherwise, $H^{\prime}$ contains a copy
of $S^{p+1}_{k_{1},\cdots,k_{q}}$, say $H_{1}$. Then $H_{1}$ has a copy of
$S^{p+1}_{k_{j_{0}}}$, say $H_{2}$, such that $vw_{1,1}\in E(H_{2})$, where
$j_{0}\in[q]$. Without loss of generality, let $j_{0}=q$. Let
$H_{3}=H_{1}\setminus H_{2}$. We first claim that $V(H_{2})\cap W=\emptyset$.
Otherwise, by Claim A in Lemma 3.7, we can find a copy of $S^{p+1}_{k_{q}}$ in
$H$, say $H_{4}$, such that $V(H_{4})\cap V(H_{3})=\emptyset$ and $H_{3}\cup
H_{4}$ is a copy of $S^{p+1}_{k_{1},\cdots,k_{q}}$ in $H$, a contradiction.

We may assume that $v$ is the center of $H_{2}$ (the case that $v$ is not the
center of $H_{2}$ can be proved similarly). As $v$ is the center of $H_{2}$
and $V(H_{2})\cap W=\emptyset$, there exist vertices
$w_{1,1},w_{1,2},\cdots,w_{1,p},w_{2,1},\cdots,w_{2,p},\cdots,$
$w_{k_{q},1},\cdots,w_{k_{q},p}\notin V_{1}\setminus W$ such that for any
$i\in[k_{q}]$, the vertex set $\\{w_{i,1},w_{i,2},\cdots,w_{i,p}\\}$ induces a
$K_{p}$ in $H$. For any $i\in[k_{q}]$ and $j\in[p]$, there is $2\leq s\leq p$
such that $w_{i,j}\in V_{s}$, then

$\displaystyle d_{V_{1}}(w_{i,j})$
$\displaystyle=d(w_{i,j})-d_{V_{s}}(w_{i,j})-(p-2)(\frac{n}{p}+\epsilon_{1}n)$
$\displaystyle\geq(\frac{p-1}{p}-\epsilon_{2})n-(q-1+k_{q}-1)-(p-2)(\frac{n}{p}+\epsilon_{1}n)$
$\displaystyle>\frac{n}{p}-\epsilon_{2}n-p\epsilon_{1}n,$

where the last second inequality holds as $L=\emptyset$, $|W|=q-1$ and
$H[V_{s}\setminus W]$ is $S_{k_{q}}$-free. Using Lemma 2.2, we have

$\displaystyle|\cap_{i\in[k_{q}],j\in[p]}N_{V_{1}}(w_{i,j})\setminus(W\cup
B_{1})|$ $\displaystyle\geq$
$\displaystyle\sum_{i\in[k_{q}],j\in[p]}d_{V_{1}}(w_{i,j})-(k_{q}p-1)|V_{1}|-|W|-|B_{1}|$
$\displaystyle>$ $\displaystyle
k_{q}p(\frac{n}{p}-\epsilon_{2}n-p\epsilon_{1}n)-(k_{q}p-1)(\frac{n}{p}+\epsilon_{1}n)-(q-1)-2k_{q}^{2}$
$\displaystyle\geq$ $\displaystyle\frac{n}{p}-o(n)$ $\displaystyle>$
$\displaystyle q(k_{1}p+1).$

Then there exists $v^{\prime}\in C_{1}$ and $v^{\prime}\notin V(H_{1})$ such
that $(H_{2}\setminus\\{v\\})\cup\\{v^{\prime}\\}$ is a copy of
$S^{p+1}_{k_{q}}$, say $H_{5}$, such that $V(H_{3})\cap V(H_{5})=\emptyset$.
Thus $H_{3}\cup H_{5}$ is a copy of $S^{p+1}_{k_{1},\cdots,k_{q}}$ in $H$, a
contradiction. Therefore, $H^{\prime}$ is $S^{p+1}_{k_{1},\cdots,k_{q}}$-free.
From the construction of $H^{\prime}$, we see that $\rho(H^{\prime})>\rho(H)$,
which contradicts the assumption that $H$ has the maximum spectral radius
among all $n$-vertex $S^{p+1}_{k_{1},\cdots,k_{q}}$-free graphs. ∎

######  Lemma 3.13.

For any $1\leq i<j\leq p$, $\left||V_{i}\setminus W|-|V_{j}\setminus
W|\right|\leq 1$.

Proof. For any $i\in[p]$, let $|V_{i}\setminus W|=n_{i}$. Suppose that
$n_{1}\geq n_{2}\geq\cdots\geq n_{p}$. We prove the assertion by
contradiction. Assume that there exist $i_{0},j_{0}$ with $1\leq
i_{0}<j_{0}\leq p$ such that $n_{i_{0}}-n_{j_{0}}\geq 2$. Let
$F=K_{p}(n_{1},n_{2},\cdots,n_{p})$ and
$F^{\prime}=K_{p}(n_{1},\cdots,n_{i_{0}}-1,\cdots,n_{j_{0}}+1,\cdots,n_{p}).$
Assume that $F^{\prime}\cong
K_{p}(n^{\prime}_{1},n^{\prime}_{2},\cdots,n^{\prime}_{p})$, where
$n^{\prime}_{1}\geq n^{\prime}_{2}\geq\cdots\geq n^{\prime}_{p}$.

Claim 1. There exists a constant $c_{1}>0$ such that

$\rho(K_{q-1}\vee T_{p}(n-q+1))-\rho(K_{q-1}\vee F)\geq\frac{c_{1}}{n}.$

Let $\mathbf{y}$ be a positive eigenvector of $K_{q-1}\vee F$ corresponding to
$\rho(K_{q-1}\vee F)$. By the symmetry we may assume
$\mathbf{y}=(\underbrace{y_{1},\cdots,y_{1}}_{n_{1}},\underbrace{y_{2},\cdots,y_{2}}_{n_{2}},\cdots,\underbrace{y_{p},\cdots,y_{p}}_{n_{p}},\underbrace{y_{p+1},\cdots,y_{p+1}}_{q-1})^{\mathrm{T}}$.
Thus by (2), we have

$\displaystyle\rho(K_{q-1}\vee
F)y_{i}=\sum_{j=1}^{p}n_{j}y_{j}-n_{i}y_{i}+(q-1)y_{p+1},\text{ for any
}i\in[p],$ (9)

and

$\displaystyle\rho(K_{q-1}\vee
F)y_{p+1}=\sum_{j=1}^{p}n_{j}y_{j}+(q-2)y_{p+1}.$ (10)

Combining (9) and (10), we have $y_{i}=\frac{\rho(K_{q-1}\vee
F)+1}{\rho(K_{q-1}\vee F)+n_{i}}y_{p+1}$ for any $i\in[p]$, which implies that
$y_{p+1}=\max\\{y_{v}:v\in V(K_{q-1}\vee F)\\}$. Without loss of generality,
we assume that $y_{p+1}=1$, then

$\displaystyle y_{i}=\frac{\rho(K_{q-1}\vee F)+1}{\rho(K_{q-1}\vee
F)+n_{i}},\text{ for any }i\in[p].$ (11)

Let $u_{i_{0}}\in V_{i_{0}}\setminus W$ be a fixed vertex. Then $K_{q-1}\vee
F^{\prime}$ can be obtained from $K_{q-1}\vee F$ by deleting all edges between
$u_{i_{0}}$ and $V_{j_{0}}\setminus W$, and adding all edges between
$u_{i_{0}}$ and $V_{i_{0}}\setminus(W\cup\\{u_{i_{0}}\\})$. According to (3),
we deduce that

$\displaystyle\rho(K_{q-1}\vee F^{\prime})-\rho(K_{q-1}\vee F)$
$\displaystyle\geq$ $\displaystyle\frac{\mathbf{y}^{\mathrm{T}}(A(K_{q-1}\vee
F^{\prime})-A(K_{q-1}\vee F))\mathbf{y}}{\mathbf{y}^{\mathrm{T}}\mathbf{y}}$
$\displaystyle=$
$\displaystyle\frac{2}{\mathbf{y}^{\mathrm{T}}\mathbf{y}}\left((n_{i_{0}}-1)y_{i_{0}}^{2}-n_{j_{0}}y_{i_{0}}y_{j_{0}}\right)$
$\displaystyle=$
$\displaystyle\frac{2y_{i_{0}}}{\mathbf{y}^{\mathrm{T}}\mathbf{y}}\left((n_{i_{0}}-1)\frac{\rho(K_{q-1}\vee
F)+1}{\rho(K_{q-1}\vee F)+n_{i_{0}}}-n_{j_{0}}\frac{\rho(K_{q-1}\vee
F)+1}{\rho(K_{q-1}\vee F)+n_{j_{0}}}\right)$ $\displaystyle=$
$\displaystyle\frac{2y_{i_{0}}}{\mathbf{y}^{\mathrm{T}}\mathbf{y}}\frac{(\rho(K_{q-1}\vee
F)+1)(n_{i_{0}}\rho(K_{q-1}\vee F)-n_{j_{0}}\rho(K_{q-1}\vee
F)-\rho(K_{q-1}\vee F)-n_{j_{0}})}{(\rho(K_{q-1}\vee
F)+n_{i_{0}})(\rho(K_{q-1}\vee F)+n_{j_{0}})}$ $\displaystyle\geq$
$\displaystyle\frac{2y_{i_{0}}}{\mathbf{y}^{\mathrm{T}}\mathbf{y}}\frac{(\rho(K_{q-1}\vee
F)+1)(\rho(K_{q-1}\vee F)-n_{j_{0}})}{(\rho(K_{q-1}\vee
F)+n_{i_{0}})(\rho(K_{q-1}\vee F)+n_{j_{0}})},$

where the last inequality holds as $n_{i_{0}}-n_{j_{0}}\geq 2$. Since
$\delta(K_{q-1}\vee F)\leq\rho(K_{q-1}\vee F)\leq\Delta(K_{q-1}\vee F)$, in
view of the construction of $K_{q-1}\vee F$, we see that $\rho(K_{q-1}\vee
F)=\Theta(n)$. Combining (11) and the fact
$\mathbf{y}^{\mathrm{T}}\mathbf{y}\leq n$, there exists a constant $c_{1}>0$
such that $\rho(K_{q-1}\vee F^{\prime})-\rho(K_{q-1}\vee
F)\geq\frac{c_{1}}{n}$, and this implies that $\rho(K_{q-1}\vee
T_{p}(n-q+1)\geq\rho(K_{q-1}\vee F^{\prime})$. Therefore, $\rho(K_{q-1}\vee
T_{p}(n-q+1))-\rho(K_{q-1}\vee F)\geq\rho(K_{q-1}\vee
F^{\prime})-\rho(K_{q-1}\vee F)\geq\frac{c_{1}}{n}$.

Claim 2. There exists a constant $c_{2}>0$ such that

$\rho(H)-\rho(K_{q-1}\vee
T_{p}(n-q+1))\geq\frac{2f(k_{q}-1,k_{q}-1)}{n}\left(1-\frac{c_{2}}{n}\right).$

Suppose that $\mathbf{z}$ is an eigenvector corresponding to $\rho(K_{q-1}\vee
T_{p}(n-q+1))$ with $\max\\{z_{v}:v\in V(K_{q-1}\vee T_{p}(n-q+1))\\}=1$. Let
$n_{1}=\lfloor\frac{n-q+1}{p}\rfloor$, $n_{2}=\lceil\frac{n-q+1}{p}\rceil$,
and $a=n-q+1-pn_{1}$. By the symmetry we may assume
$\mathbf{z}=(\underbrace{z_{1},\cdots,z_{1}}_{(p-a)n_{1}},\underbrace{z_{2},\cdots,z_{2}}_{an_{2}},\underbrace{z_{3},\cdots,z_{3}}_{q-1})^{\mathrm{T}}$.
By the similar discussion as in Claim 1, we have $z_{3}=1$,

$z_{1}=\frac{\rho(K_{q-1}\vee T_{p}(n-q+1))+1}{\rho(K_{q-1}\vee
T_{p}(n-q+1))+n_{1}}>z_{2}=\frac{\rho(K_{q-1}\vee
T_{p}(n-q+1))+1}{\rho(K_{q-1}\vee T_{p}(n-q+1))+n_{2}}>1-\frac{1}{p}.$

Let $H^{\prime}$ be a graph obtained from $K_{q-1}\vee T_{p}(n-q+1)$ by
embedding a copy of $E_{k_{q}-1,k_{q}-1}\in\mathcal{E}_{k_{q}-1,k_{q}-1}$ in
one class of $T_{p}(n-q+1)$. It is obvious that $H^{\prime}$ is
$S^{p+1}_{k_{1},\cdots,k_{q}}$-free. Therefore

$\displaystyle\rho(H)-\rho(K_{q-1}\vee T_{p}(n-q+1))$
$\displaystyle\geq\rho(H^{\prime})-\rho(K_{q-1}\vee T_{p}(n-q+1))$
$\displaystyle\geq\frac{\mathbf{z}^{\mathrm{T}}(A(H^{\prime})-A(K_{q-1}\vee
T_{p}(n-q+1)))\mathbf{z}}{\mathbf{z}^{\mathrm{T}}\mathbf{z}}$
$\displaystyle\geq\frac{2\sum_{ij\in
E(E_{k_{q}-1,k_{q}-1})}z_{i}z_{j}}{\mathbf{z}^{\mathrm{T}}\mathbf{z}}$
$\displaystyle\geq\frac{2f(k_{q}-1,k_{q}-1)z_{2}^{2}}{\mathbf{z}^{\mathrm{T}}\mathbf{z}}.$

Since $n_{2}-n_{1}\leq 1$, $an_{2}+(p-a)n_{1}=n-q+1$ and $\rho(K_{q-1}\vee
T_{p}(n-q+1))\geq\delta(K_{q-1}\vee T_{p}(n-q+1))=n-n_{2}$, we have

$\displaystyle\frac{\mathbf{z}^{\mathrm{T}}\mathbf{z}}{z_{2}^{2}}$
$\displaystyle\leq\frac{q-1}{z_{2}^{2}}+\frac{an_{2}z_{1}^{2}}{z_{2}^{2}}+(p-a)n_{1}$
$\displaystyle=\frac{q-1}{z_{2}^{2}}+an_{2}\left(\frac{\rho(K_{q-1}\vee
T_{p}(n-q+1))+n_{2}}{\rho(K_{q-1}\vee
T_{p}(n-q+1))+n_{1}}\right)^{2}+(p-a)n_{1}$
$\displaystyle=\frac{q-1}{z_{2}^{2}}+an_{2}+(p-a)n_{1}+an_{2}\left(\left(1+\frac{1}{\rho(K_{q-1}\vee
T_{p}(n-q+1))+n_{1}}\right)^{2}-1\right)$ $\displaystyle\leq
n+(q-1)\left(\frac{1}{z_{2}^{2}}-1\right)+an_{2}\left(\left(1+\frac{1}{n-1}\right)^{2}-1\right)$
$\displaystyle\leq n+c_{3},$

where $c_{3}>0$ is a constant. Therefore, for sufficiently large $n$, there
exists a constant $c_{2}>0$ such that

$\displaystyle\rho(H)-\rho(K_{q-1}\vee T_{p}(n-q+1))$
$\displaystyle\geq\frac{2f(k_{q}-1,k_{q}-1)}{n+c_{3}}$
$\displaystyle\geq\frac{2f(k_{q}-1,k_{q}-1)}{n}\frac{n}{n+c_{3}}$
$\displaystyle\geq\frac{2f(k_{q}-1,k_{q}-1)}{n}\left(1-\frac{c_{2}}{n}\right).$
(12)

Claim 3. Let $H_{in}=\cup_{i=1}^{p}H[V_{i}\setminus W]$, and
$H_{out}=(V(H)\setminus W,E(F)\setminus E(H\setminus W))$. Then
$e(H_{in})-e(H_{out})\leq f(k_{q}-1,k_{q}-1).$

We first prove that $H\setminus W$ is $S^{p+1}_{k_{q}}$-free. Suppose to the
contrary that $H\setminus W$ contains a copy of $S^{p+1}_{k_{q}}$, say
$H_{1}$. Since $|W|=q-1$ and each vertex of $W$ has degree $n-1$, $H$ has a
copy of $S^{p+1}_{k_{1},\cdots,k_{q-1}}$, say $H_{2}$, such that $V(H_{1})\cap
V(H_{2})=\emptyset$. Thus $H_{1}\cup H_{2}$ is a copy of
$S^{p+1}_{k_{1},\cdots,k_{q}}$ in $H$, and this is a contradiction. From the
definitions of $H_{in}$ and $H_{out}$, we have
$e(H_{in})=\sum_{i=1}^{p}|E(H[V_{i}\setminus W])|$ and $e(H_{out})=\sum_{1\leq
i<j\leq p}|V_{i}\setminus W||V_{j}\setminus W|-\sum_{1\leq i<j\leq
p}|E(V_{i}\setminus W,V_{j}\setminus W)|$. By Lemma 2.1, we only need to prove
that for any $i\in[p]$ and $v\in V_{i}\setminus W$,

$\displaystyle\sum_{j\neq i}\nu(H[V_{j}\setminus W])\leq k_{q}-1\ \ \
\mbox{and}\ \ \ \Delta(H[V_{i}\setminus W])\leq k_{q}-1,$ (13) $\displaystyle
d_{H[V_{i}\setminus W]}(v)+\sum_{j\neq i}\nu(H[N(v)\cap(V_{j}\setminus
W)])\leq k_{q}-1.$ (14)

Obviously (14) implies (13), so it is sufficient to prove (14). We prove (14)
by contradiction. Without loss of generality, suppose that there exists a
vertex $u\in V_{1}\setminus W$ such that

$d_{H[V_{1}\setminus W]}(u)+\sum_{j=2}^{p}\nu(H[N(u)\cap(V_{j}\setminus
W)])\geq k_{q}.$

Let $\\{w_{1}w_{2},\cdots,w_{2\ell-1}w_{2\ell}\\}$ be an $\ell$-matching of
$\cup_{j=2}^{p}H[N(u)\cap(V_{j}\setminus W)]$ and
$u_{1},\cdots,u_{k_{q}-\ell}\in V_{1}\setminus W$ be the neighbors of $u$. By
Lemma 3.12, there exist $v_{1},\cdots,v_{k_{q}-\ell}\in C_{2}$ such that
$\\{u,u_{1},\cdots,u_{k_{q}-\ell},v_{1},$
$\cdots,v_{k_{q}-\ell},w_{1},w_{2},\cdots,w_{2\ell}\\}$ induce an
$S^{3}_{k_{q}}$ of $H$. For each $u_{i}v_{i}\ (1\leq i\leq k_{q}-\ell)$, there
exist $p-2$ vertices $t_{3}\in C_{3},t_{4}\in C_{4},\cdots,t_{p}\in C_{p}$
such that $u,u_{i},v_{i},t_{3},t_{4},\cdots,t_{p}$ induce a $K_{p+1}$ of $H$.
For any $w_{i-1}w_{i}\in\\{w_{1}w_{2},\cdots,w_{2\ell-1}w_{2\ell}\\}$, without
loss of generality, suppose that $w_{i-1}w_{i}\in E(H[V_{2}\setminus W])$,
then there exist $p-2$ vertices $z_{3}\in C_{3},z_{4}\in C_{4},\cdots,z_{p}\in
C_{p}$ such that $u,w_{i-1},w_{i},z_{3},z_{4},\cdots,z_{p}$ induce a $K_{p+1}$
of $H$. Thus $H\setminus W$ contains a copy of $S^{p+1}_{k_{q}}$, which
contradicts that $H\setminus W$ is $S^{p+1}_{k_{q}}$-free.

According to the definitions of $H_{in}$, $H_{out}$ and $F$, we have
$e(H)=e(K_{q-1}\vee F)+e(H_{in})-e(H_{out})$, and $x_{v}\leq x_{v_{0}}$ for
any $v\in V(H_{in})$. By Lemma 3.12, each vertex of $C_{i}$ is adjacent to all
vertices of $V(H)\setminus V_{i}$ for any $i\in[p]$. Thus

$e(H_{out})\leq\sum_{1\leq i<j\leq
p}|B_{i}||B_{j}|<\binom{p}{2}(2k_{q}^{2})^{2}\leq 2k_{q}^{4}p^{2}.$

By Lemma 3.10, we have

$\mathbf{x}^{\mathrm{T}}\mathbf{x}\geq
n(x_{v_{0}}-\frac{100k_{1}pq}{n})^{2}\geq nx_{v_{0}}^{2}-200k_{1}pqx_{v_{0}}.$

Therefore,

$\displaystyle\rho(H)-\rho(K_{q-1}\vee F)$
$\displaystyle\leq\frac{\mathbf{x}^{\mathrm{T}}(A(H)-A(K_{q-1}\vee
F))\mathbf{x}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}$
$\displaystyle=\frac{2\sum_{ij\in
E(H_{in})}\mathbf{x}_{i}\mathbf{x}_{j}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}-\frac{2\sum_{ij\in
E(H_{out})}\mathbf{x}_{i}\mathbf{x}_{j}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}$
$\displaystyle\leq\frac{2e(H_{in})x_{v_{0}}^{2}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}-\frac{2e(H_{out})(x_{v_{0}}-\frac{100k_{1}pq}{n})^{2}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}$
$\displaystyle\leq\frac{2(e(H_{in})-e(H_{out}))x_{v_{0}}^{2}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}+\frac{2e(H_{out})\frac{200k_{1}pq}{n}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}$
$\displaystyle\leq\frac{2f(k_{q}-1,k_{q}-1)x_{v_{0}}^{2}}{nx_{v_{0}}^{2}-200k_{1}pqx_{v_{0}}}+\frac{\frac{800k_{1}k^{4}_{q}p^{3}q}{n}}{nx_{v_{0}}^{2}-200k_{1}pqx_{v_{0}}}$
$\displaystyle\leq\frac{2f(k_{q}-1,k_{q}-1)}{n-\frac{200k_{1}p^{2}q}{p-2}}+\frac{800k_{1}k^{4}_{q}p^{3}q}{n^{2}x_{v_{0}}^{2}-200k_{1}pqn}$
(15)

Combining (12) and (15), there exists a constant $c_{4}>0$ such that

$\displaystyle\rho(K_{q-1}\vee T_{p}(n-q+1))-\rho(K_{k-1}\vee F)$
$\displaystyle\leq$
$\displaystyle\frac{2f(k_{q}-1,k_{q}-1)}{n-\frac{200k_{1}p^{2}q}{p-2}}+\frac{800k_{1}k^{4}_{q}p^{3}q}{n^{2}x_{v_{0}}^{2}-200k_{1}pqn}-\frac{2f(k_{q}-1,k_{q}-1)}{n}\left(1-\frac{c_{2}}{n}\right)$
$\displaystyle<$
$\displaystyle\frac{2f(k_{q}-1,k_{q}-1)\frac{200k_{1}p^{2}q}{p-2}}{n(n-\frac{200k_{1}p^{2}q}{p-2})}+\frac{800k_{1}k^{4}_{q}p^{3}q}{n^{2}x_{v_{0}}^{2}-200k_{1}pqn}+\frac{2f(k_{q}-1,k_{q}-1)c_{2}}{n^{2}}$
$\displaystyle<$ $\displaystyle\frac{c_{4}}{n^{2}}.$

Combining with Claim 1, we have

$\displaystyle\frac{c_{1}}{n}\leq\rho(K_{q-1}\vee
T_{p}(n-q+1))-\rho(K_{q-1}\vee F)\leq\frac{c_{4}}{n^{2}},$

which is a contradiction when $n$ is sufficiently large. Thus
$\left||V_{i}\setminus W|-|V_{j}\setminus W|\right|\leq 1$ for any $1\leq
i<j\leq p$.

∎

Proof of Theorem 1.1. Now we prove that
$e(H)=\mathrm{ex}(n,S^{p+1}_{k_{1},\cdots,k_{q}})$. Otherwise, we assume that
$e(H)\leq\mathrm{ex}(n,S^{p+1}_{k_{1},\cdots,k_{q}})-1$. Let $H^{\prime}$ be
an $S^{p+1}_{k_{1},\cdots,k_{q}}$-free graph with
$e(H^{\prime})=\mathrm{ex}(n,S^{p+1}_{k_{1},\cdots,k_{q}})$. By Theorem 2.2,
$H^{\prime}$ can be obtained from $K_{q-1}\vee T_{p}(n-q+1)$ by embedding some
graph in $T_{p}(n-q+1)$. By Lemma 3.13, we may assume that
$V_{1}\cup\cdots\cup V_{p}$ is a vertex partion of $H^{\prime}$. Let
$E_{1}=E(H)\setminus E(H^{\prime})$, $E_{2}=E(H^{\prime})\setminus E(H)$, then
$E(H^{\prime})=(E(H)\cup E_{2})\setminus E_{1}$, and

$|E(H)\cap E(H^{\prime})|+|E_{1}|=e(H)<e(H^{\prime})=|E(H)\cap
E(H^{\prime})|+|E_{2}|,$

which implies that $|E_{2}|\geq|E_{1}|+1$. Furthermore, by Lemma 3.12, we have

$\displaystyle|E_{2}|=e(H^{\prime})-e(H)\leq
f(k_{q}-1,k_{q}-1)+\sum\limits_{1\leq i<j\leq
p}|B_{i}||B_{j}|<k^{2}_{q}+\binom{p}{2}(2k_{q}^{2})^{2}<3k_{q}^{4}p^{2}.$ (16)

Therefore,

$\displaystyle\rho(H^{\prime})-\rho(H)$
$\displaystyle\geq\frac{\mathbf{x}^{\mathrm{T}}(A(H^{\prime})-A(H))\mathbf{x}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}$
$\displaystyle=\frac{2\sum_{ij\in
E_{2}}\mathbf{x}_{i}\mathbf{x}_{j}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}-\frac{2\sum_{ij\in
E_{1}}\mathbf{x}_{i}\mathbf{x}_{j}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}$
$\displaystyle=\frac{2}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}\Big{(}\sum_{ij\in
E_{2}}\mathbf{x}_{i}\mathbf{x}_{j}-\sum_{ij\in
E_{1}}\mathbf{x}_{i}\mathbf{x}_{j}\Big{)}$
$\displaystyle\geq\frac{2}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}\Big{(}|E_{2}|(x_{v_{0}}-\frac{100k_{1}pq}{n})^{2}-|E_{1}|x^{2}_{v_{0}}\Big{)}$
$\displaystyle\geq\frac{2}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}\Big{(}|E_{2}|x^{2}_{v_{0}}-\frac{200k_{1}pqx_{v_{0}}}{n}|E_{2}|-|E_{1}|x^{2}_{v_{0}}\Big{)}$
$\displaystyle\geq\frac{2x_{v_{0}}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}\Big{(}x^{2}_{v_{0}}-\frac{200k_{1}pq}{n}|E_{2}|\Big{)}$
$\displaystyle\geq\frac{2x_{v_{0}}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}\Big{(}(1-\frac{2}{p})^{2}-\frac{200k_{1}pq}{n}3k_{q}^{4}p^{2}\Big{)}$
$\displaystyle>0,$

which contradicts the assumption that $H$ has the maximum spectral radius
among all $n$-vertex $S^{p+1}_{k_{1},\cdots,k_{q}}$-free graphs. Hence
$e(H)=\mathrm{ex}(n,S^{p+1}_{k_{1},\cdots,k_{q}})$. ∎

## References

  * [1] G. Chen, R. Gould, F. Pfender, B. Wei, Extremal graphs for intersecting cliques, J. Combin. Theory. Ser. B, 89 (2003) 159–171.
  * [2] V. Chvátal, D. Hanson, Degrees and matchings, J. Combin. Theory Ser. B, 20 (2) (1976) 128–138.
  * [3] S. Cioabă, D.N. Desai, M. Tait, The spectral radius of graphs with no odd wheels, European J. Combin., 99 (2022) 103420.
  * [4] S. Cioabă, L. Feng, M. Tait, X. Zhang, The maximum spectral radius of graphs without friendship subgraphs, Electron. J. Combin., 27 (4) (2020) P4.22.
  * [5] D. N. Desai, L. Kang, Y. Li, Z. Ni, M. Tait, J. Wang, Spectral extremal graphs for intersecting cliques, Linear Algebra Appl., 644 (2022) 234–258.
  * [6] R. Glebov, Extremal graphs for cliques-paths, arXiv:1111.7029v1.
  * [7] Y. Li, Y. Peng, The spectral radius of graphs with no intersecting odd cycles, Discrete Math., 345 (2022) 112907.
  * [8] H. Lin, M. Zhai, Y. Zhao, Spectral radius, edge-disjoint cycles and cycles of the same length, Electron. J. Combin., 29(2) (2022) P2.1.
  * [9] H. Liu, Extremal graphs for blow-ups of cycles and trees, Electron. J. Comb., 20 (1) (2013) P65.
  * [10] J. Moon, On independent complete subgraphs in a graph, Canad. J. Math., 20 (1968) 95–102.
  * [11] Z. Ni, L. Kang, E. Shan, H. Zhu, Extremal graphs for blow-ups of keyrings, Graphs Comb., 36 (2020) 1827–1853.
  * [12] Z. Ni, J. Wang, L. Kang, Spectral extremal graphs for disjoint cliques, Electron. J Combin., 30(1) (2023) P1.20.
  * [13] V. Nikiforov, Bounds on graph eigenvalues II, Linear Algebra Appl., 427 (2007) 183–189.
  * [14] V. Nikiforov, Stability for large forbidden subgraphs, J. Graph Theory, 62 (4) (2009) 362–368.
  * [15] V. Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl., 432 (2010) 2243–2256.
  * [16] M. Simonovits, A method for solving extremal problems in graph theory, stability problems, Theory of Graphs (Proc. colloq., Tihany, 1966), Academic Press, New York, (1968) 279–319.
  * [17] M. Simonovits, Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions, Discrete Math., 7 (1974) 349–376.
  * [18] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok, 48 (1941) 436–452.
  * [19] A. Wang, X. Hou, B. Liu, Y. Ma, The Turán number for the edge blow-up of trees, Discrete Math., 344 (2021) 112627.
  * [20] J. Wang, L. Kang, Y. Xue, On a conjecture of spectral extremal problems, J. Combin. Theory Ser. B, 159 (2023) 20–41.
  * [21] L. Yuan, Extremal graphs for edge blow-up of graphs, J. Combin. Theory Ser. B, 152 (2022) 379–398.
  * [22] M. Zhai, R. Liu, J. Xue, A Unique Characterization of Spectral Extrema for Friendship Graphs, Electron. J. Combin., 29 (3) (2022) P3.32.