We use P5 to denote a path of length 5 and C5 to denote a cycle of length 5. The aim of this paper is to prove that, if G is a connected graph satisfying (1). G has an induced C5 and no clique ...cut-set, (2). G has no induced subgraph isomorphic to P5 or K5−e, then G is max{13,ω(G)+1}-colorable.
•If a non-bipartite (P5,diamond)-free graph is not a complete graph or a 5-ring, then it contains an induced paw.•Let G be a (P5,K5−e)-free graph with an induced 5-cycle C. If G has an induced T-5-wheel Σ, then χ(G)≤max{13,ω(G)+1}.•Let G be (P5,K5−e)-free with an induced C5. Then χ(G)≤max{13,ω(G)+1}.
We use Pt and Ct to denote a path and a cycle on t vertices, respectively. A diamond is a graph obtained from two triangles that share exactly one edge. A kite is a graph that consists of a diamond ...and another vertex adjacent to a vertex of degree 2 of the diamond. A gem is a graph that consists of a P4 plus a vertex adjacent to all vertices of the P4. Choudum et al. (2021) proved that every (P7,C7,C4, gem)-free graph has either a clique cutset or a vertex whose neighbors is the union of two cliques unless it is a clique blowup of the Petersen graph, and every non-Petersen (P7,C7,C4, diamond)-free graph has either a clique cutset or has a vertex of degree at most max{2,ω(G)−1}. In this paper, we extend these two results respectively to (P7,C4, gem)-free graphs and (P7,C4, diamond)-free graphs. We also prove that if G is a (P7,C4, kite)-free graph with δ(G)≤ω(G) and without clique cutsets, then there is an integer ℓ≥0 such that G=Kℓ+H, where H is either the Petersen graph or a well-defined graph F. This implies a polynomial algorithm which can determine the chromatic number of (P7,C4, diamond)-free graphs, color (P7,C4, kite)-free graphs G with (ω(G)+1) colors, and color (P7,C4, gem)-free graphs G with (2ω(G)−1) colors.
Let $G$ be a group. The power graph of $G$ is a graph with the vertex set $G$, having an edge between two elements whenever one is a power of the other. We characterize nilpotent groups whose ...power graphs have finite independence number. For a bounded exponent group, we prove its power graph is a perfect graph and we determine its clique/chromatic number. Furthermore, it is proved that for every group $G$, the clique number of the power graph of $G$ is at most countably infinite. We also measure how close the power graph is to the commuting graph by introducing a new graph which lies in between. We call this new graph as the enhanced power graph. For an arbitrary pair of these three graphs we characterize finite groups for which this pair of graphs are equal.
Solvable conjugacy class graph of groups Bhowal, Parthajit; Cameron, Peter J.; Nath, Rajat Kanti ...
Discrete mathematics,
August 2023, 2023-08-00, Volume:
346, Issue:
8
Journal Article
Peer reviewed
Open access
In this paper we introduce the graph Γsc(G) associated with a group G, called the solvable conjugacy class graph (abbreviated as SCC-graph), whose vertices are the nontrivial conjugacy classes of G ...and two distinct conjugacy classes C,D are adjacent if there exist x∈C and y∈D such that 〈x,y〉 is solvable.
We discuss the connectivity, girth, clique number, and several other properties of the SCC-graph. One of our results asserts that there are only finitely many finite groups whose SCC-graph has given clique number d, and we find explicitly the list of such groups with d=2. We pose some problems on the relation of the SCC-graph to the solvable graph and to the NCC-graph, which we cannot solve.
On atom-bond connectivity index of graphs Hua, Hongbo; Das, Kinkar Chandra; Wang, Hongzhuan
Journal of mathematical analysis and applications,
11/2019, Volume:
479, Issue:
1
Journal Article
Peer reviewed
Open access
The atom-bond connectivity index (ABC-index) is a useful topological index employed in studying the stability of alkanes and the strain energy of cycloalkanes. The ABC-index of a nontrivial graph G, ...denoted by ABC(G), is defined as ABC(G)=∑vivj∈E(G)di+dj−2didj, where di is the degree of vertex vi in G. In this paper, we first present some lower bounds for ABC-index by means of some known inequalities. Then we give some upper bounds for ABC-index in terms of graph parameters such as clique number, vertex connectivity, algebraic connectivity and spectral radius. Moreover, we give some lower and upper bounds for ABC-index of Mycielski graphs. Finally, we compare ABC-index with other graph invariants for connected graphs.
Finding a reasonably good upper bound for the clique number of Paley graphs is an open problem in additive combinatorics. A recent breakthrough by Hanson and Petridis using Stepanov's method gives an ...improved upper bound on Paley graphs defined on a prime field Fp, where p≡1(mod4). We extend their idea to the finite field Fq, where q=p2s+1 for a prime p≡1(mod4) and a non-negative integer s. We show the clique number of the Paley graph over Fp2s+1 is at most min(ps⌈p2⌉,q2+ps+14+2p32ps−1).
Suppose that Σ is a signed graph with n vertices and m edges. Let λ1≥λ2≥⋯≥λn be the eigenvalues of Σ. A signed graph is called balanced if each of its cycles contains an even number of negative ...edges, and unbalanced otherwise. Let ωb be the balanced clique number of Σ, which is the maximum order of a balanced complete subgraph of Σ. In this paper, we prove thatλ1≤2ωb−1ωbm. This inequality extends a conjecture of ordinary graphs, which was confirmed by Nikiforov (2002) 8, to the signed case. In addition, we completely characterize the signed graphs with −1≤λ2≤0.
PDF
