Loading…
On Bipartite Graphs Having Minimum Fourth Adjacency Coefficient
Let G be a simple graph with order n and adjacency matrix A ( G ) . The characteristic polynomial of G is defined by ϕ ( G ; λ ) = det ( λ I - A ( G ) ) = ∑ i = 0 n a i ( G ) λ n - i , where a i ( G ) is called the i -th adjacency coefficient of G . Denote by B n , m the collection of all connected...
Saved in:
| Published in: | Graphs and combinatorics 2022-06, Vol.38 (3), Article 60 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c319t-28761d95df05184d5e1efb9e30647a14f28b0fb521edc1264649ea7a05beca5f3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c319t-28761d95df05184d5e1efb9e30647a14f28b0fb521edc1264649ea7a05beca5f3 |
| container_end_page | |
| container_issue | 3 |
| container_start_page | |
| container_title | Graphs and combinatorics |
| container_volume | 38 |
| creator | Gong, Shi-Cai Zhang, Li-Ping Sun, Shao-Wei |
| description | Let
G
be a simple graph with order
n
and adjacency matrix
A
(
G
)
. The characteristic polynomial of
G
is defined by
ϕ
(
G
;
λ
)
=
det
(
λ
I
-
A
(
G
)
)
=
∑
i
=
0
n
a
i
(
G
)
λ
n
-
i
, where
a
i
(
G
)
is called the
i
-th adjacency coefficient of
G
. Denote by
B
n
,
m
the collection of all connected bipartite graphs having
n
vertices and
m
edges. A bipartite graph
G
is referred as 4-Sachs optimal if
a
4
(
G
)
=
min
{
a
4
(
H
)
∣
H
∈
B
n
,
m
}
.
For any given integer pair (
n
,
m
), in this paper we investigate the 4-Sachs optimal bipartite graphs. Firstly, we show that each 4-Sachs optimal bipartite graph is a difference graph. Then we deduce some structural properties on 4-Sachs optimal bipartite graphs. Especially, we determine the unique 4-Sachs optimal bipartite (
n
,
m
)-graphs for
n
≥
5
and
n
-
1
≤
m
≤
2
(
n
-
2
)
. Finally, we provide a method to construct a class of cospectral difference graphs, which disprove a conjecture posed by Andelić et al. (J Czech Math 70:1125–1138, 2020). |
| doi_str_mv | 10.1007/s00373-022-02461-7 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2639022634</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2639022634</sourcerecordid><originalsourceid>FETCH-LOGICAL-c319t-28761d95df05184d5e1efb9e30647a14f28b0fb521edc1264649ea7a05beca5f3</originalsourceid><addsrcrecordid>eNp9kM1OwzAQhC0EEqXwApwscQ7s-iepT6hUtEUq6gXOlpPYrSuaBDtF6tvXECRuHFZ7-WZmdwi5RbhHgOIhAvCCZ8BYGpFjVpyREQouM6lQnJMRKMQMENUluYpxBwASBYzI47qhT74zofe9pYtgum2kS_Plmw199Y3fH_Z03h5Cv6XTemcq21RHOmutc77ytumvyYUzH9He_O4xeZ8_v82W2Wq9eJlNV1nFUfUZmxQ51krWLuVORC0tWlcqyyEXhUHh2KQEV0qGtq6Q5SIXyprCgCxtZaTjY3I3-Hah_TzY2OtduqpJkZrlXKXHcy4SxQaqCm2MwTrdBb834agR9HdReihKJ17_FKWLJOKDKCa42djwZ_2P6gSX92oT</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2639022634</pqid></control><display><type>article</type><title>On Bipartite Graphs Having Minimum Fourth Adjacency Coefficient</title><source>Springer Nature</source><creator>Gong, Shi-Cai ; Zhang, Li-Ping ; Sun, Shao-Wei</creator><creatorcontrib>Gong, Shi-Cai ; Zhang, Li-Ping ; Sun, Shao-Wei</creatorcontrib><description>Let
G
be a simple graph with order
n
and adjacency matrix
A
(
G
)
. The characteristic polynomial of
G
is defined by
ϕ
(
G
;
λ
)
=
det
(
λ
I
-
A
(
G
)
)
=
∑
i
=
0
n
a
i
(
G
)
λ
n
-
i
, where
a
i
(
G
)
is called the
i
-th adjacency coefficient of
G
. Denote by
B
n
,
m
the collection of all connected bipartite graphs having
n
vertices and
m
edges. A bipartite graph
G
is referred as 4-Sachs optimal if
a
4
(
G
)
=
min
{
a
4
(
H
)
∣
H
∈
B
n
,
m
}
.
For any given integer pair (
n
,
m
), in this paper we investigate the 4-Sachs optimal bipartite graphs. Firstly, we show that each 4-Sachs optimal bipartite graph is a difference graph. Then we deduce some structural properties on 4-Sachs optimal bipartite graphs. Especially, we determine the unique 4-Sachs optimal bipartite (
n
,
m
)-graphs for
n
≥
5
and
n
-
1
≤
m
≤
2
(
n
-
2
)
. Finally, we provide a method to construct a class of cospectral difference graphs, which disprove a conjecture posed by Andelić et al. (J Czech Math 70:1125–1138, 2020).</description><identifier>ISSN: 0911-0119</identifier><identifier>EISSN: 1435-5914</identifier><identifier>DOI: 10.1007/s00373-022-02461-7</identifier><language>eng</language><publisher>Tokyo: Springer Japan</publisher><subject>Apexes ; Codes ; Combinatorics ; Engineering Design ; Graph theory ; Graphs ; Mathematics ; Mathematics and Statistics ; Original Paper ; Polynomials</subject><ispartof>Graphs and combinatorics, 2022-06, Vol.38 (3), Article 60</ispartof><rights>The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature 2022</rights><rights>The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature 2022.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c319t-28761d95df05184d5e1efb9e30647a14f28b0fb521edc1264649ea7a05beca5f3</citedby><cites>FETCH-LOGICAL-c319t-28761d95df05184d5e1efb9e30647a14f28b0fb521edc1264649ea7a05beca5f3</cites><orcidid>0000-0002-0635-8308</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids></links><search><creatorcontrib>Gong, Shi-Cai</creatorcontrib><creatorcontrib>Zhang, Li-Ping</creatorcontrib><creatorcontrib>Sun, Shao-Wei</creatorcontrib><title>On Bipartite Graphs Having Minimum Fourth Adjacency Coefficient</title><title>Graphs and combinatorics</title><addtitle>Graphs and Combinatorics</addtitle><description>Let
G
be a simple graph with order
n
and adjacency matrix
A
(
G
)
. The characteristic polynomial of
G
is defined by
ϕ
(
G
;
λ
)
=
det
(
λ
I
-
A
(
G
)
)
=
∑
i
=
0
n
a
i
(
G
)
λ
n
-
i
, where
a
i
(
G
)
is called the
i
-th adjacency coefficient of
G
. Denote by
B
n
,
m
the collection of all connected bipartite graphs having
n
vertices and
m
edges. A bipartite graph
G
is referred as 4-Sachs optimal if
a
4
(
G
)
=
min
{
a
4
(
H
)
∣
H
∈
B
n
,
m
}
.
For any given integer pair (
n
,
m
), in this paper we investigate the 4-Sachs optimal bipartite graphs. Firstly, we show that each 4-Sachs optimal bipartite graph is a difference graph. Then we deduce some structural properties on 4-Sachs optimal bipartite graphs. Especially, we determine the unique 4-Sachs optimal bipartite (
n
,
m
)-graphs for
n
≥
5
and
n
-
1
≤
m
≤
2
(
n
-
2
)
. Finally, we provide a method to construct a class of cospectral difference graphs, which disprove a conjecture posed by Andelić et al. (J Czech Math 70:1125–1138, 2020).</description><subject>Apexes</subject><subject>Codes</subject><subject>Combinatorics</subject><subject>Engineering Design</subject><subject>Graph theory</subject><subject>Graphs</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Original Paper</subject><subject>Polynomials</subject><issn>0911-0119</issn><issn>1435-5914</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2022</creationdate><recordtype>article</recordtype><recordid>eNp9kM1OwzAQhC0EEqXwApwscQ7s-iepT6hUtEUq6gXOlpPYrSuaBDtF6tvXECRuHFZ7-WZmdwi5RbhHgOIhAvCCZ8BYGpFjVpyREQouM6lQnJMRKMQMENUluYpxBwASBYzI47qhT74zofe9pYtgum2kS_Plmw199Y3fH_Z03h5Cv6XTemcq21RHOmutc77ytumvyYUzH9He_O4xeZ8_v82W2Wq9eJlNV1nFUfUZmxQ51krWLuVORC0tWlcqyyEXhUHh2KQEV0qGtq6Q5SIXyprCgCxtZaTjY3I3-Hah_TzY2OtduqpJkZrlXKXHcy4SxQaqCm2MwTrdBb834agR9HdReihKJ17_FKWLJOKDKCa42djwZ_2P6gSX92oT</recordid><startdate>20220601</startdate><enddate>20220601</enddate><creator>Gong, Shi-Cai</creator><creator>Zhang, Li-Ping</creator><creator>Sun, Shao-Wei</creator><general>Springer Japan</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7TB</scope><scope>8FD</scope><scope>FR3</scope><scope>JQ2</scope><scope>KR7</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><orcidid>https://orcid.org/0000-0002-0635-8308</orcidid></search><sort><creationdate>20220601</creationdate><title>On Bipartite Graphs Having Minimum Fourth Adjacency Coefficient</title><author>Gong, Shi-Cai ; Zhang, Li-Ping ; Sun, Shao-Wei</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c319t-28761d95df05184d5e1efb9e30647a14f28b0fb521edc1264649ea7a05beca5f3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2022</creationdate><topic>Apexes</topic><topic>Codes</topic><topic>Combinatorics</topic><topic>Engineering Design</topic><topic>Graph theory</topic><topic>Graphs</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Original Paper</topic><topic>Polynomials</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Gong, Shi-Cai</creatorcontrib><creatorcontrib>Zhang, Li-Ping</creatorcontrib><creatorcontrib>Sun, Shao-Wei</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Mechanical & Transportation Engineering Abstracts</collection><collection>Technology Research Database</collection><collection>Engineering Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Civil Engineering Abstracts</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Graphs and combinatorics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Gong, Shi-Cai</au><au>Zhang, Li-Ping</au><au>Sun, Shao-Wei</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>On Bipartite Graphs Having Minimum Fourth Adjacency Coefficient</atitle><jtitle>Graphs and combinatorics</jtitle><stitle>Graphs and Combinatorics</stitle><date>2022-06-01</date><risdate>2022</risdate><volume>38</volume><issue>3</issue><artnum>60</artnum><issn>0911-0119</issn><eissn>1435-5914</eissn><abstract>Let
G
be a simple graph with order
n
and adjacency matrix
A
(
G
)
. The characteristic polynomial of
G
is defined by
ϕ
(
G
;
λ
)
=
det
(
λ
I
-
A
(
G
)
)
=
∑
i
=
0
n
a
i
(
G
)
λ
n
-
i
, where
a
i
(
G
)
is called the
i
-th adjacency coefficient of
G
. Denote by
B
n
,
m
the collection of all connected bipartite graphs having
n
vertices and
m
edges. A bipartite graph
G
is referred as 4-Sachs optimal if
a
4
(
G
)
=
min
{
a
4
(
H
)
∣
H
∈
B
n
,
m
}
.
For any given integer pair (
n
,
m
), in this paper we investigate the 4-Sachs optimal bipartite graphs. Firstly, we show that each 4-Sachs optimal bipartite graph is a difference graph. Then we deduce some structural properties on 4-Sachs optimal bipartite graphs. Especially, we determine the unique 4-Sachs optimal bipartite (
n
,
m
)-graphs for
n
≥
5
and
n
-
1
≤
m
≤
2
(
n
-
2
)
. Finally, we provide a method to construct a class of cospectral difference graphs, which disprove a conjecture posed by Andelić et al. (J Czech Math 70:1125–1138, 2020).</abstract><cop>Tokyo</cop><pub>Springer Japan</pub><doi>10.1007/s00373-022-02461-7</doi><orcidid>https://orcid.org/0000-0002-0635-8308</orcidid></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0911-0119 |
| ispartof | Graphs and combinatorics, 2022-06, Vol.38 (3), Article 60 |
| issn | 0911-0119 1435-5914 |
| language | eng |
| recordid | cdi_proquest_journals_2639022634 |
| source | Springer Nature |
| subjects | Apexes Codes Combinatorics Engineering Design Graph theory Graphs Mathematics Mathematics and Statistics Original Paper Polynomials |
| title | On Bipartite Graphs Having Minimum Fourth Adjacency Coefficient |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-08T09%3A50%3A03IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=On%20Bipartite%20Graphs%20Having%20Minimum%20Fourth%20Adjacency%20Coefficient&rft.jtitle=Graphs%20and%20combinatorics&rft.au=Gong,%20Shi-Cai&rft.date=2022-06-01&rft.volume=38&rft.issue=3&rft.artnum=60&rft.issn=0911-0119&rft.eissn=1435-5914&rft_id=info:doi/10.1007/s00373-022-02461-7&rft_dat=%3Cproquest_cross%3E2639022634%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c319t-28761d95df05184d5e1efb9e30647a14f28b0fb521edc1264649ea7a05beca5f3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2639022634&rft_id=info:pmid/&rfr_iscdi=true |