Distance Matrices and Quadratic Embedding of Graphs

a connected graph is said to be of qe class if it admits a quadratic embedding in a hilbert space, or equivalently, if the distance matrix is conditionally negative definite. several criteria for a g...

On Maximum Signless Laplacian Estrada Index of Graphs with Given Parameters II

the signless laplacian estrada index of a graph $g$ is defined as $slee(g)=\sum^{n}_{i=1}e^{q_i}$ where $q_1, q_2, \ldots, q_n$ are the eigenvalues of the signless laplacian matrix of g. following th...

Upper Bounds on the Bondage Number of a Graph

the bondage number b(g) of a graph g is the smallest number of edges whose removal from g results in a graph with larger domination number. we obtain sufficient conditions for the validity of the ineq...

Some Families of Graphs with No Nonzero Real Domination Roots

let g be a simple graph of order n. the domination polynomial of g is the polynomial $d(g, x)=\sum_{i=\gamma(g)}^{n} d(g,i) x^{i}$, where d(g,i) is the number of dominating sets of g of size i and $\g...

Computation of Gutman Index of Some Cactus Chains

let g be a finite connected graph of order n. the gutman index gut(g) of g is defined as $\sum_{\{x,y\}\subseteq v(g)}deg(x)deg(y)d(x, y)$, where deg(x) is the degree of vertex x in g and d(x, y) is t...

Computing the Edge Irregularity Strengths of Chain Graphs and the Join of Two Graphs

in computer science, graphs are used in variety of applications directly or indirectly. especially quantitative labeled graphs have played a vital role in computational linguistics, decision making so...

On Imbalances In Multipartite Multidigraphs

a $k$-partite $r$-digraph(multipartite multidigraph) (or briefly mmd)($k\geq 3$, $r\geq 1$) is the result of assigning a direction to each edge of a $k$-partite multigraph that is without loops and co...

On the Intersection Power Graph of a Finite Group

given a group g, the intersection power graph of g, denoted by $\mathcal{g}_i(g)$, is the graph with vertex set g and two distinct vertices x and y are adjacent in $\mathcal{g}_i(g)$ if there exists ...

On Classes of Neighborhood Resolving Sets of a Graph

let g=(v,e) be a simple connected graph. a subset s of v is called a neighbourhood set of g if $g=\bigcup_{s\in s}$, where n[v] denotes the closed neighbourhood of the vertex v in g. furth...

New Bounds on the Hyper-Zagreb Index for the Simple Connected Graphs

the hyper-zagreb index of a simple connected graph g is defined by ${\chi ^2}(g) = \sum_{uv \in e(g)} {{{\left( {d(u) + d(v)} \right)}^2}}$. in this paper, we establish, analyze and compare some new u...

On Inclusive Distance Vertex Irregular Labelings

for a simple graph g, a vertex labeling f:v(g)\to {1, 2, ..., k} is called a k-labeling. the weight of a vertex v, denoted by $wt_f(v)$ is the sum of all vertex labels of vertices in the closed neigh...

Formulas for the Computation of the Tutte Polynomial of Graphs with Parallel Classes

we give some reduction formulas for computing the tutte polynomial of any graph with parallel classes. several examples are given to illustrate our results.

On Size Multipartite Ramsey Numbers for Stars Versus Paths and Cycles

let $k_{l\times t}$ be a complete, balanced, multipartite graph consisting of $l$ partite sets and $t$ vertices in each partite set. for given two graphs $g_1$ and $g_2$, and integer $j\geq 2$, the si...

Traversing Every Edge in Each Direction Once, But Not at Once: Cubic (Polyhedral) Graphs

a {\em retracting-free bidirectional circuit} in a graph $g$ is a closed walk which traverses every edge exactly once in each direction and such that no edge is succeeded by the same edge in the oppos...

Efficient Maximum Matching Algorithms for Trapezoid Graphs

trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. many np-hard problems can be solved in polynomial time if they are restricted on trapezoid graphs. a matching in a ...

Restricted Size Ramsey Number for Path of Order Three Versus Graph of Order Five

let $g$ and $h$ be simple graphs. the ramsey number for a pair of graph $g$ and $h$ is the smallest number $r$ such that any red-blue coloring of edges of $k_r$ contains a red subgraph $g$ or a blue s...

Self-dual Embeddings of K_{4m,4n} in Different Orientable and Nonorientable Pseudosurfaces with the Same Euler Characteristic

a proper embedding of a graph g in a pseudosurface p is an embedding in which the regions of the complement of g in p are homeomorphic to discs and a vertex of g appears at each pinchpoint in p; we s...