Normal subgroup based power graph of finite groups

Ricerche di Matematica - Let G be a finite group and $$N \unlhd G$$ . The normal subgroup based power graph of G, $$\Gamma _N(G)$$ , is an undirected graph with vertex set $$(G{\setminus }N) \cup...     

On the order supergraph of the power graph of a finite group

Ricerche di Matematica - The power graph $${\mathcal {P}}_{G}$$ of a finite group G is the graph whose vertex set is G, two distinct vertices are adjacent if one is a power of the other. The order...     

Perfect Domination Polynomial of Homogeneous Caterpillar Graphs and of Full Binary Trees

Mathematical Notes - Let $$G=(V,E)$$ be a simple graph of order $$n$$ . A set $$S \subseteq V(G)$$ is a perfect dominating set of a graph $$G$$ if every vertex $$v\in V(G)-S$$ is adjacent to...     

Weighted Triangle-free 2-matching Problem with Edge-disjoint Forbidden Triangles

Mathematical Programming - The weighted $${\mathcal {T}}$$ -free 2-matching problem is the following problem: given an undirected graph G, a weight function on its edge set, and a set $${\mathcal...     

Lambda number of the power graph of a finite group

Journal of Algebraic Combinatorics - The power graph $$\Gamma _G$$ of a finite group G is the graph with the vertex set G, where two distinct elements are adjacent if and only if one is a power of...     

On the critical difference of almost bipartite graphs

Journal of Algebraic Combinatorics - A set $$S\subseteq V$$ is independent in a graph $$G=\left( V,E\right) $$ if no two vertices from S are adjacent. The independence number $$\alpha (G)$$ is the...     

The Divisibility Graph for F-Groups

Mathematical Notes - A graph $$D(G)$$ is called the divisibility graph of $$G$$ if its vertex set is the set of noncentral conjugacy class sizes of $$G$$ and there is an edge between vertices $$a$$...     

Extremal Problems on Components and Loops in Graphs

The authors recently defined a new graph invariant denoted by Ω(G) only in terms of a given degree sequence which is also related to the Euler characteristic. It has many important combinatorial applications in graph theory and gives direct information compared to the better known Euler characteristic on the realizability, connectedness, cyclicness, components, chords, loops etc. Many similar classification problems can be solved by means of Ω. All graphs G so that Ω(G) ≤-4 are shown to be disconnected, and if Ω(G) ≥-2, then the graph is potentially connected. It is also shown that if the realization is a connected graph and Ω(G) =-2, then certainly the graph should be a tree.Similarly, it is shown that if the realization is a connected graph G and Ω(G) ≥ 0, then certainly the graph should be cyclic. Also, when Ω(G) ≤-4, the components of the disconnected graph could not all be cyclic and if all the components of G are cyclic, then Ω(G) ≥ 0. In this paper, we study an extremal problem regarding graphs. We find the maximum number of loops for three possible classes of graphs.We also state a result giving the maximum number of components amongst all possible realizations of a given degree sequence.     

Random Schreier graphs and expanders

Journal of Algebraic Combinatorics - Let the group G act transitively on the finite set $$\Omega $$ , and let $$S \subseteq G$$ be closed under taking inverses. The Schreier graph $$Sch(G...     

On toric ideals arising from signed graphs

Journal of Algebraic Combinatorics - A signed graph is a pair $$(G,\tau )$$ of a graph G and its sign $$\tau $$ , where a sign $$\tau $$ is a function from $$\{ (e,v)\mid e\in E(G),v\in V(G), v\in...     

Convergence Towards the End Space for Random Walks on Schreier Graphs

Journal of Theoretical Probability - We consider a transitive action of a finitely generated group G and the Schreier graph $$\varGamma $$ defined by this action for some fixed generating set. For...     

On the Inertia Index of a Mixed Graph in Terms of the Matching Number

Acta Mathematicae Applicatae Sinica, English Series - A mixed graph $${\tilde G}$$ is obtained by orienting some edges of G, where G is the underlying graph of $${\tilde G}$$ . The positive inertia...     

The Hamilton-Connectivity with the Degree Sum of Non-adjacent Subgraphs of Claw-free Graphs

Acta Mathematicae Applicatae Sinica, English Series - The degree d(H) of a subgraph H of a graph G is $$|\underset{u \in V(H)}{\cup} N(u)-V(H)|$$ , where N(u) denotes the neighbor set of the vertex...     

Vertex-edge domination in graphs

Aequationes mathematicae - We establish that for any connected graph G of order $$n \ge 6$$ , a minimum vertex-edge dominating set of G has at most n/3 vertices, thus affirmatively answering the...     

Path-pairability of infinite planar grids

Periodica Mathematica Hungarica - For a given integer $$k\ge 1$$ , a graph G with at least 2k vertices is called k-path-pairable, if for any set of k disjoint pairs of vertices, $$s_i,t_i$$ ,...     

On the location of zeros of the Laplacian matching polynomials of graphs

Journal of Algebraic Combinatorics - The Laplacian matching polynomial of a graph G, denoted by $$\mathscr {LM}(G,x)$$ , is a new graph polynomial whose all zeros are nonnegative real numbers. In...     

The domination game played on diameter 2 graphs

Aequationes mathematicae - Let $$\gamma _g(G)$$ be the game domination number of a graph G. It is proved that if $$\mathrm{diam}(G) = 2$$ , then $$\gamma _g(G) \le \left\lceil \frac{n(G)}{2}...     

On path-factor critical deleted (or covered) graphs

Aequationes mathematicae - Let $$k\ge 2$$ be an integer. A $$P_{\ge k}$$ -factor of a graph G is its spanning subgraph each of whose components is a path of order at least k. A graph G is $$P_{\ge...     

The Distinguishing Numbers and the Distinguishing Indexes of Cayley Graphs

Journal of Applied and Industrial Mathematics - The distinguishing number (index) $$D(G)$$ ( $$D^{\prime }(G) $$ ) of a graph $$G $$ is the least integer $$d $$ such that $$G $$ has a vertex...     

On the Second Smallest and the Largest Normalized Laplacian Eigenvalues of a Graph

Acta Mathematicae Applicatae Sinica, English Series - Let G be a simple connected graph with order n. Let $$\mathcal{L}(G)$$ and $$\mathcal{Q}(G)$$ be the normalized Laplacian and normalized...