On the Laplacian Coefficients of Tricyclic Graphs with Prescribed Matching Number

Jing Luo; Zhongxun Zhu; Runze Wan

Displaying similar documents to “On the Laplacian Coefficients of Tricyclic Graphs with Prescribed Matching Number”

Structure of the set of all minimal total dominating functions of some classes of graphs

K. Reji Kumar, Gary MacGillivray (2010)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we study some of the structural properties of the set of all minimal total dominating functions ( $_{T}$ ) of cycles and paths and introduce the idea of function reducible graphs and function separable graphs. It is proved that a function reducible graph is a function separable graph. We shall also see how the idea of function reducibility is used to study the structure of $_{T} (G)$ for some classes of graphs.

Symmetries of embedded complete bipartite graphs

Erica Flapan, Nicole Lehle, Blake Mellor, Matt Pittluck, Xan Vongsathorn (2014)

Fundamenta Mathematicae

Similarity:

We characterize which automorphisms of an arbitrary complete bipartite graph $K_{n, m}$ can be induced by a homeomorphism of some embedding of the graph in S³.

Metrically regular square of metrically regular bipartite graphs of diameter $D = 7$

Vladimír Vetchý (2018)

Archivum Mathematicum

Similarity:

The present paper deals with the spectra of powers of metrically regular graphs. We prove that there is only two tables of the parameters of an association scheme so that the corresponding metrically regular bipartite graph of diameter $D = 7$ (8 distinct eigenvalues of the adjacency matrix) has the metrically regular square. The results deal with the graphs of the diameter $D < 7$ see [8], [9] and [10].

Stable sets for $(P ₆, K_{2, 3})$ -free graphs

Raffaele Mosca (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for $(P ₆, K_{2, 3})$ -free graphs in polynomial time, extending some known results.

A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs

Yury Metelsky, Kseniya Schemeleva, Frank Werner (2017)

Discussiones Mathematicae Graph Theory

Similarity:

We characterize the class [...] L32 $L_{3}^{2}$ of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 $L_{3}^{2}$ in the class of threshold graphs, where n is the number of vertices of a tested graph.

On the signless Laplacian spectral characterization of the line graphs of $T$ -shape trees

Guoping Wang, Guangquan Guo, Li Min (2014)

Czechoslovak Mathematical Journal

Similarity:

A graph is determined by its signless Laplacian spectrum if no other non-isomorphic graph has the same signless Laplacian spectrum (simply $G$ is $D Q S$ ). Let $T (a, b, c)$ denote the $T$ -shape tree obtained by identifying the end vertices of three paths $P_{a + 2}$ , $P_{b + 2}$ and $P_{c + 2}$ . We prove that its all line graphs $ℒ (T (a, b, c))$ except $ℒ (T (t, t, 2 t + 1))$ ( $t \geq 1$ ) are $D Q S$ , and determine the graphs which have the same signless Laplacian spectrum as $ℒ (T (t, t, 2 t + 1))$ . Let $μ_{1} (G)$ be the maximum signless Laplacian eigenvalue of the graph $G$ . We give the limit of $μ_{1} (ℒ (T (a, b, c)))$ , too.

The order of uniquely partitionable graphs

Izak Broere, Marietjie Frick, Peter Mihók (1997)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition V₁,...,Vₙ of V(G) such that, for each i = 1,...,n, the subgraph of G induced by $V_{i}$ has property $_{i}$ . If a graph G has a unique (₁,...,ₙ)-partition we say it is uniquely (₁,...,ₙ)-partitionable. We establish best lower bounds for the order of uniquely (₁,...,ₙ)-partitionable graphs, for various choices of ₁,...,ₙ.

On hereditary properties of composition graphs

Vadim E. Levit, Eugen Mandrescu (1998)

Discussiones Mathematicae Graph Theory

Similarity:

The composition graph of a family of n+1 disjoint graphs $H_{i} : 0 \leq i \leq n$ is the graph H obtained by substituting the n vertices of H₀ respectively by the graphs H₁,H₂,...,Hₙ. If H has some hereditary property P, then necessarily all its factors enjoy the same property. For some sort of graphs it is sufficient that all factors $H_{i} : 0 \leq i \leq n$ have a certain common P to endow H with this P. For instance, it is known that the composition graph of a family of perfect graphs is also a perfect graph (B. Bollobas, 1978),...

On Ramsey $(K_{1, 2}, K ₙ)$ -minimal graphs

Mariusz Hałuszczak (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let F be a graph and let , denote nonempty families of graphs. We write F → (,) if in any 2-coloring of edges of F with red and blue, there is a red subgraph isomorphic to some graph from G or a blue subgraph isomorphic to some graph from H. The graph F without isolated vertices is said to be a (,)-minimal graph if F → (,) and F - e not → (,) for every e ∈ E(F). We present a technique which allows to generate infinite family of (,)-minimal graphs if we know some special graphs. In particular,...

Clopen graphs

Stefan Geschke (2013)

Fundamenta Mathematicae

Similarity:

A graph G on a topological space X as its set of vertices is clopen if the edge relation of G is a clopen subset of X² without the diagonal. We study clopen graphs on Polish spaces in terms of their finite induced subgraphs and obtain information about their cochromatic numbers. In this context we investigate modular profinite graphs, a class of graphs obtained from finite graphs by taking inverse limits. This continues the investigation of continuous colorings on Polish spaces and their...

On 2-periodic graphs of a certain graph operator

Ivan Havel, Bohdan Zelinka (2001)

Discussiones Mathematicae Graph Theory

Similarity:

We deal with the graph operator $\bar{P o w ₂}$ defined to be the complement of the square of a graph: $\bar{P o w ₂} (G) = \bar{P o w ₂ (G)}$ . Motivated by one of many open problems formulated in [6] we look for graphs that are 2-periodic with respect to this operator. We describe a class of bipartite graphs possessing the above mentioned property and prove that for any m,n ≥ 6, the complete bipartite graph $K_{m, n}$ can be decomposed in two edge-disjoint factors from . We further show that all the incidence graphs of Desarguesian finite projective...

On the minimal basis of the spindle-surface $g e r m S_{1}$ .

R. Bodendiek, K. Wagner (1989)

Banach Center Publications

Similarity:

On Ramsey $(K_{1, 2}, C ₄)$ -minimal graphs

Tomás Vetrík, Lyra Yulianti, Edy Tri Baskoro (2010)

Discussiones Mathematicae Graph Theory

Similarity:

For graphs F, G and H, we write F → (G,H) to mean that any red-blue coloring of the edges of F contains a red copy of G or a blue copy of H. The graph F is Ramsey (G,H)-minimal if F → (G,H) but F* ↛ (G,H) for any proper subgraph F* ⊂ F. We present an infinite family of Ramsey $(K_{1, 2}, C ₄)$ -minimal graphs of any diameter ≥ 4.

Bounding the Openk-Monopoly Number of Strong Product Graphs

Dorota Kuziak, Iztok Peterin, Ismael G. Yero (2018)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V, E) be a simple graph without isolated vertices and minimum degree δ, and let k ∈ 1 − ⌈δ/2⌉, . . . , ⌊δ/2⌋ be an integer. Given a set M ⊂ V, a vertex v of G is said to be k-controlled by M if [...] δM(v)≥δG(v)2+k $δ_{M} (v) \geq \frac{δ_{G} (v)}{2} + k$ , where δM(v) represents the number of neighbors of v in M and δG(v) the degree of v in G. A set M is called an open k-monopoly if every vertex v of G is k-controlled by M. The minimum cardinality of any open k-monopoly is the open k-monopoly number of G. In this...

Finite groups whose character degree graphs coincide with their prime graphs

Temha Erkoç, Utku Yilmaztürk, İsmail Ş. Güloğlu (2018)

Czechoslovak Mathematical Journal

Similarity:

In the literature, there are several graphs related to a finite group $G$ . Two of them are the character degree graph, denoted by $Δ (G)$ , and the prime graph, $Γ (G)$ . In this paper we classify all finite groups whose character degree graphs are disconnected and coincide with their prime graphs. As a corollary, we find all finite groups whose character degree graphs are square and coincide with their prime graphs.

The hull number of strong product graphs

A.P. Santhakumaran, S.V. Ullas Chandran (2011)

Discussiones Mathematicae Graph Theory

Similarity:

For a connected graph G with at least two vertices and S a subset of vertices, the convex hull ${[S]}_{G}$ is the smallest convex set containing S. The hull number h(G) is the minimum cardinality among the subsets S of V(G) with ${[S]}_{G} = V (G)$ . Upper bound for the hull number of strong product G ⊠ H of two graphs G and H is obtainted. Improved upper bounds are obtained for some class of strong product graphs. Exact values for the hull number of some special classes of strong product graphs are obtained. Graphs...

Rotation and jump distances between graphs

Gary Chartrand, Heather Gavlas, Héctor Hevia, Mark A. Johnson (1997)

Discussiones Mathematicae Graph Theory

Similarity:

A graph H is obtained from a graph G by an edge rotation if G contains three distinct vertices u,v, and w such that uv ∈ E(G), uw ∉ E(G), and H = G-uv+uw. A graph H is obtained from a graph G by an edge jump if G contains four distinct vertices u,v,w, and x such that uv ∈ E(G), wx∉ E(G), and H = G-uv+wx. If a graph H is obtained from a graph G by a sequence of edge jumps, then G is said to be j-transformed into H. It is shown that for every two graphs G and H of the same order (at least...

Main eigenvalues of real symmetric matrices with application to signed graphs

Zoran Stanić (2020)

Czechoslovak Mathematical Journal

Similarity:

An eigenvalue of a real symmetric matrix is called main if there is an associated eigenvector not orthogonal to the all-1 vector $𝐣$ . Main eigenvalues are frequently considered in the framework of simple undirected graphs. In this study we generalize some results and then apply them to signed graphs.

Independent cycles and paths in bipartite balanced graphs

Beata Orchel, A. Paweł Wojda (2008)

Discussiones Mathematicae Graph Theory

Similarity:

Bipartite graphs G = (L,R;E) and H = (L’,R’;E’) are bi-placeabe if there is a bijection f:L∪R→ L’∪R’ such that f(L) = L’ and f(u)f(v) ∉ E’ for every edge uv ∈ E. We prove that if G and H are two bipartite balanced graphs of order |G| = |H| = 2p ≥ 4 such that the sizes of G and H satisfy ||G|| ≤ 2p-3 and ||H|| ≤ 2p-2, and the maximum degree of H is at most 2, then G and H are bi-placeable, unless G and H is one of easily recognizable couples of graphs. This result implies easily that...